Binary search

二分法。

一般 pattern

low = 0
high = n
while low <= high:
    mid = (low + high) // 2
    mid_calc = f(mid)
    if mid_calc == target:
        return g(mid)
    elif mid_calc < target:
        low = mid + 1
    else:
        high = mid - 1
return default_retval

注意 low <= high, low = mid + 1 和 high = mid - 1。while 循环结束后 low 的值是新元素的插入位置。

变化

mid 赋值为 floor((left + right) / 2) 时，需要用 left = mid + 1 和 right = mid，循环判断为 left < right

合并大于和等于的情况

如需找到元素第一次出现的下标（Leetcode 34. Find First and Last Position of Element in Sorted Array），可将 mid_calc 等于和大于的情况合并，并给新的 high 赋值时不 + 1。

C++ 示例：

int lower_bound(vector<int> &nums, int target) {
    int low = 0;
    int high = nums.size();
    int mid;
    while (low < high) {
        mid = low + (high - low) / 2;
        if (nums[mid] >= target) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}