二分查找 | Notes

二分查找算法-折半查找算法

二分思想

二分查找针对的是一个有序的数据集合，查找思想类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

查找速度O(logn)

数组：
假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是除以2。最坏情况下，直到查找区间被缩小为空才停止。被查找区间的大小变化n,n/2,n/4,n/8,…,n/2^k…为一个等比数列，当n/2^k=1时，k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以经过了k次区间缩小操作，时间复杂度就是O(k)。通过n/2^k，可以求得k=log₂n，所以时间复杂度就是O(logn)。

对数时间复杂度是一直极其高效的时间复杂度，有的时候甚至常量级时间复杂度的算法还要高效。

链表：
假设链表长度为n，二分查找每次都要找到中间结点：
第一次查找中间结点需要移动指针n/2次;
第二次，需要移动n/4次；
第三次，需要n/8次；
。。。
以此类推，一直到1次为止。
指针一共移动次数k=n/2+n/4+n/8+…+1，等比数列求和为n-1。
时间复杂度为O(n)。与顺序查找时间复杂度相同。但二分查找需要进行多余的运算，比顺序查找慢。

递归与非递归实现

最简单的情况就是有序数组中不存在重复元素，用二分查找值等于给定值的数据。

//非递归
public int bsearch(int[] a,int value) {
    int low = 0;
    int high = a.length-1;
    while(low <= high) {
        int mid = (low+high) / 2;
        if(a[mid] == value) {
            return mid;
        } else if(a[mid] < value) {
            low = mid + 1;
        } else {
            high = mid -1;
        }
    }
    return -1;
}

low、high、mid都是指数组下标，low和high表示当前查找的区间范围，初始low=0,high=n-1。mid表示[low,high]的中间位置，通过a[mid]与value的大小，来更新接下来要查找的区间范围，直到找到或者区间缩小为0就退出。

循环退出条件
low<=high
mid取值
mid=(low+high)/2。
low + (high - low) /2;避免low和high比较大时，两者和溢出。
将除以2转化成位运算low+((high-low)>>1)。注意位运算优先级
low和high的更新
low=mid+1&high=mid-1。
low=mid|high=mid可能发生死循环。

//递归
public int bsearch(int[] a,int value) {
    return bserachInter(a,0,a.length-1,value);
}

private int bserachInter(int[] a,int low,int high,int value) {
    if(low > high) return -1;
    int mid = low + ((high-low)>>1);
    if(a[mid] == value) {
        return mid;
    } else if(a[mid] < value) {
        return bserachInter(a,mid+1,high,value);
    } else {
        return bserachInter(a,low,high+1,value);
    }
}

应用场景局限性

二分查找依赖的是顺序表结构-数组
二分查找算法需要按照下标随机访问数组。数组按照下标随机访问数据的时间复杂度是O(1)，链表随机访问的时间复杂度是O(n)。如果数据使用链表存储，二分查找的时间复杂度会变得很高。
二分查找只能用在数据是通过顺序表来存储的数据结构上，如果数据是通过其他数据结构存储的，则无法使用二分查找。
二分查找针对的是有序数据
数据必须是有序的。如果数据无序，需要先排序，排序的时间复杂度最低是O(nlogn)。如果针对的是一组静态的数据，没有频繁的插入、删除，可以进行一次排序、多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。
数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。针对动态数据，无论什么方法，维护有序的成本都很高。(二叉树)
数据量太小不适合二分查找
数据量很小，顺序便利足够。但是数据之间的比较操作非常耗时，不管数据量大小，都推荐二分查找，尽可能的减少比较次数，大大提高性能。
数据量太大不适合二分查找
二分查找底层依赖数组这种数据结构，数组为了支持随机访问特性，要求内存空间连续，对内存的要求比较苛刻。即使拥有更多的内存空间剩余，如果是零散的不连续，依然无法申请相应大小的数组。