二分查找

二分查找有左闭右开和左闭右闭两种写法,均需要掌握。

左闭右闭:

定义 target 在 [left, right] 区间,所以有如下两点:

  • while (left <= right) 要使用 <= ,因为 left === right 是有意义的,所以使用 <=
  • if (nums[mid] > target) right 要赋值为 mid - 1,因为当前这个 nums[mid] 一定不是target,那么接下来要查找的左区间结束下标位置就是 mid - 1
function search(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1
  while (left <= right) {
    const mid = ((right - left) >> 1) + left
    if (nums[mid] > target) {
      right = mid - 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      return mid
    }
  }
  return -1
}

左闭右开:

定义 target 在 [left, right) 区间,所以有如下两点:

  • while (left < right) 要使用 < ,因为 left === right 在区间 [left, right) 是没有意义的,所以使用 <
  • if (nums[mid] > target) right 更新为 mid,因为当前 nums[mid] 不等于 target,去左区间继续寻找,而寻找区间是左闭右开区间,所以 right 更新为 mid,因为下一个查询区间依然不会去比较 nums[mid]
function search(nums: number[], target: number): number {
  let left = 0, right = nums.length
  while (left < right) {
    const mid = ((right - left) >> 1) + left
    if (nums[mid] > target) {
      right = mid
    } else if (nums[mid] < target) {
      left = mid + 1
    } else {
      return mid
    }
  }
  return -1
}
©2022 Flower-F. All Rights Reserved.
Built based on Takuya Matsuyama's website.