📚 XXY的学习笔记

二分查找基础

2026年2月27日
已完成
算法 二分查找 搜索
📝 CodePen在新窗口打开 →

概念理解

二分查找（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它的核心思想是通过不断将搜索范围减半来快速定位目标元素。

为什么叫”二分”？

因为每次比较后，我们都会将搜索范围缩小为原来的一半：

  • 如果目标值小于中间值，搜索左半部分
  • 如果目标值大于中间值，搜索右半部分
  • 如果相等，找到目标

时间复杂度

  • 最优时间复杂度: O(1) - 第一次就找到
  • 平均时间复杂度: O(log n)
  • 最坏时间复杂度: O(log n)

可视化演示

下面是一个二分查找的可视化演示，帮助你理解算法的执行过程：

代码实现

基础版本

def binary_search(arr, target):
    """
    在有序数组中查找目标值

    Args:
        arr: 有序数组
        target: 目标值

    Returns:
        目标值的索引，如果不存在则返回 -1
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

JavaScript 版本

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

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

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

  return -1;
}

// 使用示例
const nums = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(nums, 7)); // 输出: 3

常见变体

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

def find_first_equal(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] >= target:
            if arr[mid] == target:
                result = mid
            right = mid - 1
        else:
            left = mid + 1

    return result

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

def find_last_equal(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            if arr[mid] == target:
                result = mid
            left = mid + 1
        else:
            right = mid - 1

    return result

常见陷阱

  1. 整数溢出: 使用 mid = left + (right - left) // 2 而不是 (left + right) // 2
  2. 边界条件: 注意 left <= right 还是 left < right
  3. 更新边界: left = mid + 1 和 right = mid - 1，不要漏掉 +1 或 -1

学习心得

  1. 二分查找看似简单，但边界条件很容易出错
  2. 建议使用”循环不变量”的方法来确定边界条件
  3. 多练习不同变体，理解其本质
  4. 画图是理解二分查找的好方法

相关题目