二分查找

前提

目标函数有单调性，或者能通过条件排除一半答案
存在上下界
能够通过索引访问

模板一：闭区间查找

适合找一个确定的值，找到就返回。

function binarySearch(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)

    if (nums[mid] === target) return mid
    if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return -1
}

对应题目：

1. 二分查找
1. 搜索旋转排序数组

0704. 二分查找

function search(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)

    if (nums[mid] === target) return mid
    if (nums[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return -1
}

0033. 搜索旋转排序数组

旋转数组不是整体有序，但每次二分后，左右两边至少有一边是有序的。

function search(nums: number[], target: number): number {
  let left = 0
  let right = nums.length - 1

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] === target) return mid

    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1
      } else {
        right = mid - 1
      }
    }
  }

  return -1
}

模板二：夹逼

适合找边界、最小值、峰值这类题。核心是答案一直在 [left, right] 中，每次排除一边。

let left = 0
let right = nums.length - 1

while (left < right) {
  const mid = left + Math.floor((right - left) / 2)

  if (check(mid)) {
    right = mid
  } else {
    left = mid + 1
  }
}

return left

对应题目：

1. 在排序数组中查找元素的第一个和最后一个位置
1. 寻找旋转排序数组中的最小值
1. 寻找峰值
1. 搜索二维矩阵 II

0034. 在排序数组中查找元素的第一个和最后一个位置

找左边界：第一个 >= target 的位置。

找右边界：第一个 >= target + 1 的位置，再减一。

function searchRange(nums: number[], target: number): number[] {
  const left = lowerBound(nums, target)
  const right = lowerBound(nums, target + 1) - 1

  if (left === nums.length || nums[left] !== target) return [-1, -1]

  return [left, right]
}

function lowerBound(nums: number[], target: number): number {
  let left = 0
  let right = nums.length

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)

    if (nums[mid] >= target) {
      right = mid
    } else {
      left = mid + 1
    }
  }

  return left
}

0153. 寻找旋转排序数组中的最小值

用 nums[mid] 和 nums[right] 比较，判断最小值在哪一边。

function findMin(nums: number[]): number {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)

    if (nums[mid] > nums[right]) {
      left = mid + 1
    } else {
      right = mid
    }
  }

  return nums[left]
}

0162. 寻找峰值

看 mid 和 mid + 1 的坡度，往更高的一侧走。

function findPeakElement(nums: number[]): number {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)

    if (nums[mid] > nums[mid + 1]) {
      right = mid
    } else {
      left = mid + 1
    }
  }

  return left
}