README.md

二分算法

二分查找是用于在有序数组中进行 $\log n$ 复杂度的数据查找

C++ 标准库加成

使用 lower_bound 来查找第一个不小于待查元素的位置 和 upper_bound 来查找第一个大于待查元素的位置

手动实现

大致模板如下所示，根据实际场景调整

while (l < r) {
    int mid = (l + r)>>1;
    if (mid == target) return mid;
    else if (mid > target) {
        l = mid+1;
    } else {
        r = mid;
    }
}

二分的使用分为二分结果和二分输入两种

二分结果

例如leetcode668中，间接使用二分，不断二分结果，判断然后在内部判断该结果rank，尽管二分范围内的数据不是完全有序的，但是其在行上是有序的。可以利用这一特性辅助二分。