二分查找

查找

二分查找

算法思想

※二分的本质并不是单调性 有单调性一定可以二分 用二分的不一定有单调性
※二分的本质是找边界点 每次二分时选择答案所在区间 当区间长度为1时 得出答案
※若有某种性质使得一部分满足 另一部分不满足,二分可以用来寻找这个性质边界(两个边界对应两个模板)
※整数二分需要考虑边界问题，浮点二分不需要考虑边界问题。
**当l = mid 时 mid = l + r + 1 >> 1;**
当r = mid 时 mid = l + r >> 1;

模板代码

bool check(mid) {/* ... */};// 检查mid是否满足某种性质
//右半区间成立 二分右边的分界点
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;        
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

//左半区间成立 二分左边的分界点
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;       //向上取整
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

完整代码

### 整数二分
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n,m;
int q[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n;i ++){
        scanf("%d",&q[i]);
    }
    while(m --){
        int x;
        scanf("%d",&x);
        int l = 0,r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(q[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if(q[l] != x) cout << "-1 -1" << endl;
        else{
            cout << l <<' ';
            int l = 0, r = n-1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(q[mid] <= x) l =mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
        return 0;
    }

### 浮点二分（求某个浮点数的平方根）
#include<iostream>
using namespace std;
int main(){
    int x;
    scanf("%d",&x);
    double l = 0,r = x;
    while(r - l > 1e-8){
        double mid = (l + r) / 2;
        if(mid*mid >= x) r = mid;
        else l = mid;
    }
    printf("%lf\n",l);
    return 0;
}
}

算法书写过程

★先写mid = l + r >> 1;
★在确定check函数；
★最后根据所写出的l与r的值确定mid是否要加1，防止边界问题

分析边界问题
▲若当l = mid 时， 没有取 mid = l + r + 1 >>1 向上取整，而是取mid = l + r >> 1 向下取整
当l = r - 1时，mid = l，若此时check函数返回值为true，则此时跟新的区间为[l,r];所以此次循环并没有改变区间，则下次循环也不会改变区间，也就是进入了死循环
▲当mid取了 mid = l + r + 1 >> 1时，则mid = r，则此时更新的区间为[r,r],就会停止循环了，不会进入死循环了.