二分专题

10模型

// 类似 1 1 1 1 1 1  1 1 key 0 0 0 0 0 0 0 0的二分查找 查找最后一个1

//区间 [1, n]
int binary_search(int *arr, int head, int tail) { //可以理解为查找小于key的最大数
    int l = head, r = tail;
    while (l < r) {
        int mid = (l + r + 1) >> 1;  //+1操作防止特殊情况（1 1）陷入死循环
        if (arr[mid] >= key) r = mid - 1;
        else l = mid;
    }

}

01模型

// 类似0 0 0 0 0 0 0 0 key 1 1 1 1 1 1  1 1 的二分查找 查找第一个1

//区间 [1, n]
int binary_search(int *arr, int head, int tail) { //可以理解为查找大于key的最小数
    int l = head, r = tail;
    while (l < r) {
        int mid = (l + r) >> 1; 
        if (arr[mid] <= key) l = mid + 1;
        else r = mid;
    }

}

小数二分

//区间 [1, n]

#define INF 0.000001

double binary_search(double *arr, doulbe head, double tail) {
    double l = head, r = tail;
    while (r - l > INF) { //l与r近视相等
        int mid = (l + r) / 2; 
        if (arr[mid] != 1) r = mid;
        else l = mid;
    }
}