搜索算法

🔍 二分搜索

二分搜索是最经典的 O(log n) 算法，面试必考。

🔍二分搜索

搜索目标:

速度:

L (left)

R (right)

M (mid)

找到

已排除

// 二分搜索 - 迭代版

function binarySearch(arr, target) {

let left = 0, right = arr.length - 1;

while (left <= right) {

// 防止整数溢出

const mid = left + Math.floor((right - left) / 2);

if (arr[mid] === target) return mid;

if (arr[mid] < target) left = mid + 1;

else right = mid - 1;

}

return -1;

}

📊 复杂度分析

时间: O(log n) - 每次排除一半

空间: O(1) 迭代 / O(log n) 递归

为什么是 log n?

n 个元素，每次减半:

n → n/2 → n/4 → ... → 1

需要 log₂(n) 次才能减到 1

🎯 核心要点

前提条件

数组必须有序
如果无序，先排序 O(n log n)，或使用线性搜索 O(n)

三个关键边界

// 1. 循环条件: <= 不是 <
while (left <= right) {

  // 2. 防止整数溢出
  const mid = left + Math.floor((right - left) / 2);
  // 不要写成 (left + right) / 2，可能溢出

  if (arr[mid] === target) return mid;

  // 3. 缩小范围: +1 和 -1，不是 mid
  if (arr[mid] < target) left = mid + 1;
  else right = mid - 1;
}

为什么是 O(log n)？

每次比较后，搜索范围减半：

n → n/2 → n/4 → n/8 → ... → 1

需要 log₂(n) 次才能将 n 减到 1。

n	log₂(n)	最多比较次数
10	3.3	4
100	6.6	7
1,000	10	10
1,000,000	20	20

100 万个元素只需 20 次比较！

🔄 变体问题

1. 查找第一个等于 target 的位置

function findFirst(arr, target) {
  let left = 0, right = arr.length - 1, result = -1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] >= target) {
      if (arr[mid] === target) result = mid;
      right = mid - 1; // 继续向左找
    } else {
      left = mid + 1;
    }
  }
  return result;
}

2. 查找最后一个等于 target 的位置

function findLast(arr, target) {
  let left = 0, right = arr.length - 1, result = -1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] <= target) {
      if (arr[mid] === target) result = mid;
      left = mid + 1; // 继续向右找
    } else {
      right = mid - 1;
    }
  }
  return result;
}

3. 旋转数组搜索 (LeetCode #33)

function searchRotated(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;

    // 判断哪半边是有序的
    if (arr[left] <= arr[mid]) {
      // 左半边有序
      if (arr[left] <= target && target < arr[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 右半边有序
      if (arr[mid] < target && target <= arr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}

🔗 相关知识

复杂度分析 - 理解 O(log n)
排序算法 - 二分搜索的前提
递归 - 二分搜索的递归实现