二分法专题

二分法常见的几种题目类型

• 查找特定值
• 查找第一个大于(或等于)特定值的元素 – 「找下界」
• 查找最后一个小于(或等于)特定值的元素 – 「找上界」

二分法通用模板

二分查找无论是找下界、还是找上界、还是找特定值，都可以套用「找下界」的模板代码：

• 循环条件为 left <= right，表示闭区间不为空
• if 的判定条件和给定的比较规则是一致的：比如要找满足 x >= target 的第一个元素，就令 if nums[m] >= target；要找满足 x > target 的第一个元素，就令 if nums[m] > target
• if 为真时，更新 right：right = mid - 1；否则 left = mid + 1
• 当循环结束时，left 就指向下界，right 指向「互补条件」的上界

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] >= target {  // 此处需要条件与题目要求一致
            right = mid-1
        } else {
            left = mid+1
        }
    }
    return left
}

互补条件: 上述模板中left代表的是大于等于target的第一个元素， right代表的是小于target的最后一个元素。因此可以将取上界问题转换为其互补的取下界问题，并将返回值改为right

题目列表

题目链接	描述
1539. 第 k 个缺失的正整数	二分法取上界问题变形