二分

算法

• 对排好序的序列才可以使用二分
• 使用方式 1. 操作序列上的值，2. 操作序列下标

1. 取序列中点下标 或 值 mid = l + r >> 1
2. 判断p[mid] 或 mid 与目标值 x的判定条件，如果大于等于、小于等于，则更新左、右端点的值为mid
3. 在新的另一半序列中继续判定，终止条件为l >= r（即l == r时，得到目标结果）

二分查找的判定、更新过程：

c++实现

// 二分查找模板，此处是查下标
int binary_search(int x, int l, int r) {
    
    while (l < r) {
        mid = l + r + 1 >> 1;
        if (p[mid] <= x) l = mid;	// 改变判定条件，交换扫描方向，得到某个数范围
        else r = mid - 1;
    }
}

// 二分查找数值，数的三次方根
double binary_search_num(double x) {
    double l = -100;
    double r = 100;
    while (r - l > 1e-8) 
        {  // 一般比精确的位数大两个数量级，这里是直接数字二分，不是idx作为二分的目标
            double mid = (l + r) / 2;
            if (mid * mid * mid >= n) r = mid;
            else l = mid;
        }
    return l;
}

tip

1. 有时候在一个序列中，x的值可能有连续多个，而上述这样查找的只有单方向的一个结果，如上面得到的是从右向左看的结果。
2. 要在if的判定条件换位p[mid] >= x，是从左朝右看的第一个的结果

复杂度

• 时间复杂度是log(n)
• 空间复杂度是n