二分查找
二分查找有左闭右开和左闭右闭两种写法,均需要掌握。
左闭右闭:
定义 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 }