二分查找及其变体

写法细节

1 . 取中点的表达式采用分式写法： M = L + (R - L) / 2; ，可以有效防止下标超出整数范围。

2 . 取中点的表达式向上取整： M = L + (R - L + 1)/2;; ，可以有效防止在相邻的两个元素中陷入死循环。

向上/向下取整

1 . 如果代码中是用的L = M，把L不断往右push，那么M向上取整（M = L + (R - L + 1)/2）；

2 . 如果代码中是用的R = M，把R不断往左push，那么M向下取整（M = L + (R - L)/2）。

查找x

 int L = 0, R = n-1;          // 数组下标从0到n-1，闭区间
    while( L <= R ) {             // 当区间中至少有两个数字的时候，需要继续二分
        int M = L + (R - L) / 2; // 求出区间中点
        if (a[M == x) return M;
        if( a[M] < x ) {         // 答案一定出现在[M+1,R]中
            L = M+1;
        } else {                 // a[M] >= x，答案一定出现在[L,M]中
            R = M;
        }
    }
    return -1;

最后一个小于等于x的数字

写法一

int L = 0, R = n - 1;
    while( L < R ) {
        int M = L + (R - L)/2;
        if( a[M] <= x ) { 
            L = M + 1;
        } else { // 答案在[L,M]中
            R = M;
        }
    }

    if ( a[L] == x) {
        cout << L << endl;  // 如果答案存在，则输出答案
    } else {
        cout << -1 << endl; // 如果答案不存在，则输出-1
    }

写法二
取中点M的表达式一定要+1，否则可能会陷入死循环：

int L = 0, R = n-1;
while( L < R ) {
    int M = L + (R - L + 1)/2;
    if( a[M] <= x ) { // 答案一定在[M,R]中
        L = M;
    } else { // 答案一定在[L,M - 1]中
        R = M - 1;
    }
}

查找日期

应用场景
若把发生事件A的日期记录在某个数组中，现在想知道在某日期是否发生了事件A，那么就需要在日期数组中查找该特定的日子。

查找两个日期的中点
若日期表示成YYYYMMDD的形式，比如公元1年1月1日就是00010101，1000000000年1月1日就是10000000000101，经过一定的特殊处理后，可以在日期数列中使用二分法查找某一个日期。
二分法查找日期查找日期最主要的一个问题就是如何找到两个日期的合法中值。可以采取向下取整的方法，例如，如果我们得到了类似于19971805这样不合法的日期（没有18月），我们只需要把18月向下取整到合法的日期（12月），变为19971205即可。

统计x出现的次数

可以直接使用c++实现好的 lower_bound 和 upper_bound ，这两个函数都是采用二分法实现的。

#include 
using namespace std;

int n = 10;
int a[10] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};

int main() {
    
    sort(a, a+n);   // 对a数组进行排序
    int q = 3;      // 询问3次
    while( q-- ) {  // 回答q次询问
        int x;
        cin >> x;   // 请在代码区下方的输入区依次输入3个你想要查询的数。
                    // 比如，1，2，3，注意中间要空格，或换行输入
        int *lp = lower_bound(a, a + n, x); // 第一个大于等于x的数字的指针
        int *rp = upper_bound(a, a + n, x); // 第一个大于x的数字的指针
        cout << int(rp-lp) << endl;       // 指针相减得到区间长度
    }
    return 0;
}

二分法求解方程

求解f(x) = 0 的解。

较低精度

#include 
using namespace std;

double f( double x ) {
    return x * x * x + 16; // 某个函数f(x)
}
double solve() {
    double L = -1e9, R = 1e9; // 方程解在[L,R]之间，且函数在[L,R]上单调增
    while( R - L >= 1e-6 ) { // 精确到6位小数，然后四舍五入
        double m = L + (R - L) / 2;
        if (f(m) < 0) L = m;
        else R = m;
    }
    return L;
} 
  
int main() {
    printf( "%.5lfn", solve() );
    return 0;
}

高精度

当要求高精度时，while( R - L >= 1e-11 ) 这种控制误差的方式可能会陷入死循环。这是因为double本身时存在误差的。

因此，在高精度的情况下，可以采取固定二分次数的方法来取得合理的结果。若初始条件是1e9左右，要求精度控制在1e-20，可以二分100次。这是因为2的100次方约为1e30，而我们二分的初始条件是1e9左右，足以在最后把精度控制在1e-20左右。

参考：青舟智学

二分查找及其变体

C/C++/C#相关栏目本月热门文章