跳到主要内容

二分查找

定义​

每一次查找将整个区间分为左右两边，根据中点的值来判断要查找的值应当在哪一侧。

用途​

用于查找左右两部分的分界点，可以是左半边的边界，也可以查找右半边的边界。

举个例子
在一个升序的序列中，查找数字5，那么整个序列可以将其划分为两部分，左边全部小于等于5，右边全部大于5，这就是上面说的适用条件，这个性质不一定是唯一的，例如：左边全部小于5，右边全部大于等于5。那么现在查找数字5，可以看作是查找左半边的右边界，也可也是查找右半边的左边界。

适用范围​

有某种性质，可以将整个序列分割成左右两部分

实现​

整数二分​

  • 思路

  选择中间的点作为分界点，根据该点的值与要查找的值进行对比判断要查找的值在哪个区域，然后缩小区域继续查找。

  • 时间复杂度：O(log2n)O(log_2n)
int binary_search(int q[], int l, int r, int search) 
{
    int loc, mid;
    while(l < r) {
        mid = (l + r) >> 1;
        if(q[mid] >= search) {r = mid;}
        else l = mid + 1;
    }
    //找到了右半边的左边界，此时 l == r，都停留在右半边的左边界处
    if(q[l] == search) loc = l;
    else loc = -1;
    return loc;
}
题目链接
注意点1

代码行高亮的地方需要注意是用 (l+r)/2 还是 (l+r+1)/2。可以试想一下，假如我求的是左半边的右边界，并且此时左半边的性质是<= x，当区间仅剩两个元素的时候，如果mid = (l + r) / 2，并且第一个元素满足 q[mid] <= x，此时会陷入无限循环当中。

注意点2

二分法是一定能够找到边界点的，二分法执行到最后 l == r 的时候就已经找到了边界点，这个边界点就是 l 或者 r ，但是边界点是否满足题目要求这是不一定的。

小数二分​

  • 思路

  小数二分其实与整数二分思路一样，依旧是将区间分成两部分，然后通过不断缩小搜索区间来找到要找的值。

  但小数二分与整数二分区别在于，小数二分的分界点可以是小数，并且左右边区间不需要考虑类似 r=mid−1r = mid -1 这种问题，因此每一次划分的左右区间都是 [l,mid][l, mid] 和 [mid,r][mid, r]

  • 时间复杂度：O(log2n)O(log_2n)
#define MAX 10000
#define MIN -10000

//查找某一个数的三次方根
double binary_search(double n)
{
    double l = MIN, r = MAX;
    double mid;
    //这里 r - l >= 1e-8 是因为题目要求输出六位小数，
    //当满足要求时，无论 l 和 r 怎么变化，mid前6位小数都不会发生改变
    while(r - l >= 1e-8){
        mid = (l + r) / 2;
        if(mid*mid*mid >= n) r = mid;
        else l = mid;
    }
    return mid;
}
相关题目
0%