完备区间判断下的二分查找万能模板

• 场景
• 二分模板
  • 整数二分
    • C++
    • Python
  • 浮点数二分

场景

单调数列/数组 一定可以用二分；但如果非单调的情况，也有可能存在能够使用二分的情况

---

二分模板

整数二分

C++

#include <iostream>

// 整数二分的模板
bool check(int x) {/*......*/} // 检查x是否满足某种性质

/*
    目前发现整数二分的所有情况都可以被下面的两个板子涵盖
*/

// 2.1.1 区间被划分成 [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;
        else l = mid + 1;
    }
    return l
}

// 2.1.2 区间被划分成 [l, mid - 1] 和 [mid, r]
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (chedk(mid)) l = mid;
        else r = mid - 1;
    }
}

Python

#  二分查找
def check(x):  # 判断x是否满足某种性质
    if x > 0:
        return True
    else:
        return False

# 2.1.1 区间被划分成 [l, mid] 和 [mid + 1， r]
def bsearch_2(l, r):
    while l < r:
        mid = l + r >> 1
        if (check(mid)):
            r = mid
        else:
            l = mid + 1
    return l

# 2.1.2 区间被划分成 [l, mid - 1] 和 [mid, r]
def bsearch_1(l, r):
    while l < r:
        mid = l + r + 1 >> 1
        if (check(mid)):
            l = mid
        else:
            r = mid - 1
    return l

浮点数二分

只有C++要考虑，高贵的Python不需要考虑。

#include <iostream>

double bsearch_3(double l, double r) {
    const double eps = 1e-6;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}