二分搜索总结

Basic Binary Search

class Solution:
  def searchInsert(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
      mid = (left + right) // 2
      if nums[mid] < target:
        left = mid + 1
      elif nums[mid] > target:
        right = mid - 1
      else:
        return mid
    return left

几个需要注意的点：

  1. 循环结束条件是<=。
  2. 为避免死循环，每次循环都需要改变上下界的值。
  3. 如果target不存在，结束时状态一定为left > right且二者相差一，这时left的位置就是应该插入的索引。
  4. Java和Cpp中 (left + right) / 2可以写为left + (right - left) / 2。
· 面试笔记