二分查找

二分查找细节是魔鬼。

while (left <= right)与while (left < right)

取决于你的区间是闭区间[0,len-1]，还是左闭右开 [0,len)

left = mid + 1，right = mid与left = mid + 1，right = mid - 1

[0,len)分成[left,mid),[mid+1,right)

[0,len-1]分成[left,mid-1],[mid+1,right]

在有序数组中查找目标元素

function binarySearch(nums: number[], target: number) {
  const Len = nums.length
  let left = 0, right = Len - 1
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] == target) {
      return mid
    } else if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1
    }
  }
  return -1
}

目标元素的左边界

if (nums[mid] === target) right = mid - 1向左收缩

function left_binarySearch(nums: number[], target: number) {
  const Len = nums.length
  let left = 0, right = Len - 1
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) {
      right = mid - 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1
    }
  }
  if (nums[left] !== target || left === Len) return -1
  return left
}

目标元素的右边界

if (nums[mid] === target) left = mid + 1向右收缩

function right_binarySearch(nums: number[], target: number) {
  const Len = nums.length
  let left = 0, right = Len - 1
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === target) {
      left = mid + 1
    } else if (nums[mid] < target) {
      left = mid + 1
    } else if (nums[mid] > target) {
      right = mid - 1
    }
  }
  if (nums[right] !== target || right === Len) return -1
  return right
}

参考

代码和思路都参考二分查找细节详解，顺便赋诗一首

YBFACC / blog

二分查找 #44