📚 二分查找

在 42 亿个有序数据中用二分查找一个数据，最多需要比较 32 次。二分查找是一个时间复杂度为 O(logn) 的算法。logn 非常“恐怖”，即便 n 非常非常大，对应的 logn 也很小。

二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

  • 被查找区间的大小变化
    n, n/2, n/4, n/8 … n/2^k

  • 使用场景

    • 目标函数单调性（单调递增或者递减）
    • 存在上下界
    • 能够通过索引访问


💻 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var binarySearch = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    let mid = left + ((right - left) >> 1); // 相当于 Math.floor(left + (right - left) / 2)
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
};


🏫 经典题目

主要包括这 3 类

  1. 简单的有序数组中查找元素
  2. 用于旋转后的、二维的有序数组
  3. 查找“近似值”问题


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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
const binarySearch = (nums, target, lower) => {
  let left = 0,
    right = nums.length - 1,
    ans = nums.length;
  while (left <= right) {
    const mid = right + ((right - left) >> 1);
    // lower为true时，找最左一个位置，nums[mid] === target时，让right往下减，最后找到最左侧的索引
    // lower为false时，找最后一个位置, nums[mid] === target, 让left往上加，最后找到大于target的索引
    if (nums[mid] > target || (lower && nums[mid] >= target)) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

const searchRange = (nums, target) => {
  let ans = [-1, -1];
  const leftIdx = binarySearch(nums, target, true);
  const rightIdx = binarySearch(nums, target, false) - 1;
  if (
    nums[leftIdx] === target &&
    nums[rightIdx] === target &&
    leftIdx >= 0 &&
    rightIdx < nums.length
  ) {
    ans = [leftIdx, rightIdx];
  }
  return ans;
};