基础模板(Basic)
二分查找

二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是用来在一个有序数组中查找某一元素的算法。

bool check(int x) {/* ... */} // 检查 x 是否满足某种性质
// 区间 [l, r] 被划分成 [l, mid] 和 [mid + 1, r] 时使用:
int binary_search_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 binary_search_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;
}