↓跳过正文
Tequila’s 学习笔记
  1. 全部/
  2. 笔记/
  3. LeetCode/

1 二分查找

目录

找下界：满足 x ≥ target 的第一个元素
#

func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums)-1 // 闭区间 [left, right]
    for left <= right {           // 区间不为空
        // 循环不变量：
        // nums[left-1] < target
        // nums[right+1] >= target
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}
  • 循环条件为 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 指向「互补条件」的上界
  1. x >= target (lowerBound)
  2. x > target –> (lowerBound(target+1))
  3. x < target –> (lowerBound(target)-1)
  4. x <= target –> (lowerBound(target+1)-1)
Reply by Email