标准二分查找

二分查找最重要的不是 mid 怎么写，而是你要先固定区间定义，并在整个循环里保持这个定义不被破坏。

算法原理

二分查找（Binary Search）是一种在有序数组中高效查找目标值的算法。

核心思想

• 每次比较中间元素，排除一半的搜索空间
• 将搜索范围缩小为原来的 1/2

前提条件

1. 数组必须是有序的（升序或降序）
2. 数组支持随机访问（能通过索引直接访问）

时间复杂度

• 最好：O(1) - 第一次就找到
• 平均：O(log n)
• 最坏：O(log n)

空间复杂度

• O(1) - 只需要常数空间

🎞️ 动画演示

（附件 binary-search.gif 未随站点发布）

看动画时关注不变量

每一步开始时，如果目标存在，它一定仍在 [left, right] 中。比较 nums[mid] 后，被排除的那一半不可能再包含答案。

Go 代码

Go 实现

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
 
    for left <= right {
        mid := left + (right-left)/2
 
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
 
    return -1
}

为什么这样写

[left, right] 这套写法维护的循环不变量是：

• 如果目标存在，它一定还在当前闭区间里。
• 当 nums[mid] < target 时，mid 不可能是答案，左半边也都可以排除。
• 当 nums[mid] > target 时，mid 不可能是答案，右半边也都可以排除。

所以更新一定是：

• left = mid + 1
• right = mid - 1

而不是含糊地“缩一下范围”。

算法步骤演示

查找目标值 7：

初始: [1, 3, 5, 7, 9, 11, 13]
       L              M               R

比较: nums[3]=7, 找到目标！

查找目标值 6：

步骤1: [1, 3, 5, 7, 9, 11, 13]
        L              M               R
        nums[3]=7 > 6, 向左搜索

步骤2: [1, 3, 5, 7]
        L     M     R
        nums[1]=3 < 6, 向右搜索

步骤3: [5, 7]
        L=M  R
        nums[2]=5 < 6, 向右搜索

步骤4: [7]
        L>R, 结束

结果: -1（未找到）

关键点

1. 边界条件选择

区间类型	while条件	right初始化	right更新
[left, right]	left <= right	len(nums) - 1	mid - 1
[left, right)	left < right	len(nums)	mid

3. 循环不变量

确保每次循环后，目标值（如果存在）一定在 [left, right] 区间内。

易错点

二分查找最容易错的不是思路，而是边界。

• [left, right] 和 [left, right) 不能混写。
• 求左边界、右边界时，更新规则会变。
• mid 最好写成 left + (right-left)/2，避免溢出。
• 二分答案题里，比较的往往不是数组值，而是“某个条件是否成立”。

相关题目

LeetCode练习

• LeetCode 704 - 二分查找

  • 难度：简单
  • 标准的二分查找模板题

• LeetCode 35 - 搜索插入位置

  • 难度：简单
  • 查找目标值的插入位置

扩展阅读

• 左边界查找 - 查找第一个等于target的位置
• 右边界查找 - 查找最后一个等于target的位置
• 旋转数组搜索 - 在旋转数组中的二分查找

---

返回：搜索算法