深入浅出二分查找算法

一，简单的二分查找算法

二分查找（Binary Search）算法是一种针对有序且不含重复数据集合的查找算法，时间复杂度为 $O(logn)$ ，二分查找虽然性能比较优秀，但应用场景也比较有限。

因为底层依赖于数组这种结构，所以不适合数据量大的情况。再次，对于较小规模的数据查找，二分查找的优势并不明显，一般直接使用顺序遍历就可以了。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

如果数据使用链表存储，二分查找的时间复杂就会变得很高，变成了 $O(n)$。

简单的二分查找算法的 C++ 代码如下：

// 非递归实现
int BinarySearch(int a[], int n, int value){
    int low = 0, high = n-1;
    int mid = (low+high)/2;
    while( low <= high){
        // mid = low+(high-low)/2; mid = low+((high-low)>>1)
        mid = (low+high)/2;

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

注意：二分查找算法的核心是在于利用二分思想，每次都与区间的中间数据比对大小，缩小查找区间的范围。二分查找算法除了用上面的循环实现，实际上还可以用递归实现。简单二分查找算法的递归代码如下：

int BinarySearch(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 BinarySearch(a, low, mid-1, value);
    else return BinarySearch(a, mid + 1, high, value);
}

二，二分查找算法的变形

4 种常见的二分查找变形问题：

1. 查找第一个值等于给定值的元素；
2. 查找最后一个值等于给定值的元素；
3. 查找第一个值大于等于给定值的元素；
4. 查找最后一个值小于等于给定值的元素；

其实以上四个问题都针对的是有序数据集合中存在重复的数据的情况

因为是有序数组，所以这个重复的隐含线索是连续重复数据。

2.1，变体一：查找第一个值等于给定值的元素

根据前文实现的简单二分查找代码，我们知道 a[mid] 跟要查找的 value 的大小关系有三种情况：大于、小于、等于。对于 a[mid]>value 的情况，我们需要更新 high= mid-1；对于 a[mid]<value 的情况，我们需要更新 low=mid+1。这两点和简单二分查找代码一样，但是当 a[mid]=value 时，二分查找算法的变形有着不同的处理形式。

二分查找问题不同的人有着不同的解决方法，第一个二分查找变形问题的简洁实现方法如下：

int BinarySearch(int a[], int n, int value){
    int low = 0, high = n-1;
    while(low <= high){
        int mid =  low + ((high - low) >> 1);
        if(a[mid] > value){
            high = mid - 1;
        }
        else if(a[mid] < value){
            low = mid + 1 ;
        }
        else{
            if(mid == 0 || a[mid - 1] != value) return mid;
            else high = mid -1;
        }
    }
    return -1;
}

2.2，变体二：查找最后一个值等于给定值的元素

这个问题和上个问题类似，只需在上面代码基础上，稍作修改即可。

int BinarySearch(int a[], int n, int value){
    int low = 0, high = n-1;
    while(low <= high){
        int mid =  low + ((high - low) >> 1);
        if(a[mid] > value){
            high = mid - 1;
        }
        else if(a[mid] < value){
            low = mid + 1 ;
        }
        else{
            if(mid == n-1 || a[mid + 1] != value) return mid;
            else low = mid + 1; // 更新 low=mid+1，因为要找的元素肯定出现在[mid+1, high]之间
        }
    }
    return -1;
}

2.3，变体三：查找第一个大于等于给定值的元素

实际上，实现的思路跟前面的那两种变形问题的实现思路是类似的，但是代码写起来甚至更简洁，因为考虑的情况要少一种了，a[mid] > value 和 a[mid] = value 可以放在一个 if 分支里面，分支里面的处理语句和前面代码类似。

int BinarySearch(int a[], int n, int value){
    int low = 0, high = n-1;
    while(low <= high){
        int mid =  low + ((high - low) >> 1);
        if(a[mid] >= value){
            if(mid == 0 || a[mid - 1] < value) return mid;
            else high = mid -1;
        }
        else {
            low = mid + 1 ;
        }
    }
    return -1;

如果 a[mid] 小于要查找的值 value，那要查找的值肯定在 [mid+1, high] 之间，所以，我们更新 low=mid+1。

对于 a[mid] 大于等于给定值 value 的情况，我们要先看下这个 a[mid]是不是我们要找的第一个值大于等于给定值的元素。如果 a[mid] 前面已经没有元素，或者前面一个元素小于要查找的值 value，那 a[mid]就是我们要找的元素。这段逻辑对应的代码是第 7 行。

如果 a[mid-1] 也大于等于要查找的值 value，那说明要查找的元素在 [low, mid-1] 之间，所以，我们将 high 更新为 mid-1。

2.4，变体四：查找最后一个小于等于给定值的元素

有了前面的基础，这个问题的代码就可以直接写出来了，复制上文代码，修改第 7、8 行即可。

int BinarySearch(int a[], int n, int value){
    int low = 0, high = n-1;
    while(low <= high){
        int mid =  low + ((high - low) >> 1);
        if(a[mid] > value){
            high = mid - 1;
        }
        else {
            if(mid == high || a[mid + 1] > value) return mid;
            else low = mid + 1;
        }
    }
    return -1;

三，总结

二分查找的核心思想理解起来非常简单，有点类似分治思想。即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为 0。其代码有三个容易出错的地方：循环退出条件、mid 的取值，low 和 high 的更新。

凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多。二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。

四，二分查找算法解题模板

1，二分查找模板1:

将区间 [l, r] 划分成 [l, mid] 和 [mid+1, r] 时，其更新操作是 r = mid 或 l = mid + 1;，计算 mid 时不需要加1.

int bsearch_1(int l, int r){
    while (l < r){
        int mid = (l + r) >> 1; // (l + r)/2 向下取整
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

2，二分查找模板2:

将区间 [l, r] 划分成 [l, mid-1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或 l = mid;，为了防止死循环，计算 mid 时需要加1.

int bsearch_1(int l, int r){
    while (l < r){
        int mid = (l + r + 1) >> 1; // (l + r)/2 向上取整
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

版权声明©

• 本文作者：嵌入式视觉
• 版权声明：本文为「嵌入式视觉」的原创文章，首发于 github ，遵循 CC BY-NC-ND 4.0 版权协议，著作权归作者所有，转载请注明出处！
• 鼓励博主：如果看完文章有所收获，一定要先点赞后收藏。毕竟，赠人玫瑰，手有余香!