🔍 二分查找 — 精准定位的艺术

O(log n)的搜索奇迹，每一步砍掉一半可能性

📖 二分查找的核心概念

二分查找（Binary Search）是一种在有序序列中高效查找的算法。每一步将搜索范围缩小一半，时间复杂度为 O(log n)。虽然概念简单，但边界条件的处理是面试中最容易出错的环节之一——据统计，90% 的程序员无法一次写出正确的二分查找。

二分查找的核心流程: 有序数组: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 目标: 11 第1轮: [1, 3, 5, 7, 9, |11|, 13, 15, 17, 19] left=0 mid=4 right=9 nums[4]=9 < 11 → 搜索右半部分第2轮: [_, _, _, _, _, |11|, 13, 15, 17, 19] left=5 mid=7 right=9 nums[7]=15 > 11 → 搜索左半部分第3轮: [_, _, _, _, _, |11|, 13, _, _, _] left=5 mid=5 right=6 nums[5]=11 = 11 → 找到！返回 5 每一步砍掉一半 → O(log n)

1. 两种二分模板

模板一：精确查找（找目标值）
循环条件：left <= right
找到目标直接返回，否则返回 -1
适用：确认目标值是否存在

模板二：边界查找（找左边界/右边界）
循环条件：left < right
找到目标不返回，继续缩小范围
适用：找第一个 ≥ target 的位置、找最后一个 ≤ target 的位置

2. 二分查找的易错点

mid = left + (right - left) // 2，不用 (left + right) // 2 避免溢出
循环条件：<= 还是 <？取决于区间定义（闭区间还是半开区间）
更新边界：left = mid + 1 还是 left = mid？取决于 mid 是否可能为答案
死循环：当 left = right - 1 时，如果 left = mid，mid 仍等于 left，死循环！

3. 何时使用二分查找？

二分查找不限于有序数组！核心前提是搜索空间具有单调性——即存在一个分界点，一侧满足条件，另一侧不满足。

场景	单调性体现	示例
有序数组查找	值单调递增	LC 35, LC 704
旋转数组查找	两段分别有序	LC 33
求第K小/大	答案单调	LC 378
最小化最大值	判定函数单调	LC 410
求局部峰值	相邻差单调	LC 162

🎯 题目一：搜索插入位置 (LC 35)

题目描述：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

示例: nums = [1, 3, 5, 6], target = 5 → 返回 2 示例: nums = [1, 3, 5, 6], target = 2 → 返回 1 示例: nums = [1, 3, 5, 6], target = 7 → 返回 4 核心思想: 找第一个 ≥ target 的位置这就是"左边界"查找!

思路分析

左边界二分：找第一个 ≥ target 的位置。
1. 如果 target 存在，就是 target 的位置
2. 如果 target 不存在，就是插入位置
循环结束后，left 就是答案。
时间复杂度：O(log n)，空间复杂度：O(1)

代码实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

复杂度分析

时间复杂度：O(log n) — 每次砍半

空间复杂度：O(1) — 只用几个变量

变体练习

LC 704 二分查找（基础版本）
LC 34 在排序数组中查找元素的第一个和最后一个位置

🎯 题目二：搜索旋转排序数组 (LC 33)

题目描述：整数数组 nums 按升序排列，数组中的值互不相同，在传递给函数之前在某个下标处旋转。给你旋转后的数组和一个目标值 target，如果 nums 中存在这个目标值，返回它的下标，否则返回 -1。

示例: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 旋转后: 两段分别有序 [4, 5, 6, 7 | 0, 1, 2] 第一段↑ 第二段↑ 二分时判断哪一半有序: mid=3, nums[3]=7, nums[0]=4 7 ≥ 4 → 左半 [4,5,6,7] 有序 target=0 < 4 → target不在左半 → 搜索右半 mid=5, nums[5]=1, nums[4]=0 1 ≥ 0 → 左半 [0,1] 有序 target=0 在 [0,1] 中 → 搜索左半 mid=4, nums[4]=0 = target → 找到! 返回4

思路分析

旋转数组二分：关键观察——旋转数组从 mid 切开，必有一半是有序的。
1. 比较 nums[mid] 和 nums[left]，判断哪一半有序
2. 如果左半有序（nums[mid] ≥ nums[left]）：检查 target 是否在左半范围
3. 如果右半有序：检查 target 是否在右半范围
4. 每次排除一半，O(log n)
时间复杂度：O(log n)，空间复杂度：O(1)

代码实现

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] >= nums[left]:  # 左半有序
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:  # 右半有序
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

复杂度分析

时间复杂度：O(log n) — 标准二分

空间复杂度：O(1)

有重复元素的旋转数组（LC 81）更复杂：当 nums[mid] == nums[left] 时无法判断哪半有序，需要 left++ 逐步缩小范围，最坏 O(n)。

变体练习

LC 81 搜索旋转排序数组 II（有重复元素）
LC 153 寻找旋转排序数组中的最小值

🎯 题目三：寻找峰值 (LC 162)

题目描述：给定一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，返回任何一个峰值的位置即可。你可以假设 nums[-1] = nums[n] = -∞。

示例: nums = [1, 2, 3, 1] 位置: 0 1 2 3 数值: [1, 2, 3, 1] ↑ 峰值! 3 > 2 且 3 > 1 二分思路: 如果 nums[mid] < nums[mid+1] → 右侧一定有峰值 → left = mid + 1 如果 nums[mid] > nums[mid+1] → mid可能是峰值 → right = mid 因为边界是-∞，所以"爬坡"一定能到峰值!

思路分析

爬坡二分：这道题数组不有序，但依然可以用二分！
核心观察：比较 nums[mid] 和 nums[mid+1]：
- 如果上升（nums[mid] < nums[mid+1]），右侧必有峰值（因为右边最终会下降到 -∞）
- 如果下降（nums[mid] > nums[mid+1]），mid 可能就是峰值，或左侧有峰值
- 这就是"单调性"——虽然数组不单调，但"峰值的存在性"有单调性
时间复杂度：O(log n)，空间复杂度：O(1)

代码实现

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
        return left

复杂度分析

时间复杂度：O(log n)

空间复杂度：O(1)

这道题是"二分不限于有序数组"的经典例子！关键在于发现搜索空间的单调性：mid 和 mid+1 的大小关系决定了峰值在哪一侧。

变体练习

LC 852 山脉数组的峰顶索引（严格先增后减）
LC 1095 山脉数组中查找目标值（先二分找峰，再两侧分别二分）

成就解锁：二分猎人 — 掌握精确查找、边界查找、旋转数组和峰值查找四种二分变形

LeetCode AC验证：LC 35 Search Insert Position ✅ | LC 33 Search in Rotated Sorted Array ✅ | LC 162 Find Peak Element ✅

📝 课后练习

LC 704 二分查找（基础模板练习）
LC 34 排序数组中查找首末位置（左右边界）
LC 69 x 的平方根（二分猜答案）
LC 367 有效的完全平方数
LC 410 分割数组的最大值（二分答案 + 贪心判定）

🔑 本课要点回顾

二分查找核心：每步砍半，O(log n)
精确查找：left <= right，找到即返回
边界查找：left < right，找到继续缩小，最后 left 是答案
mid 防溢出：mid = left + (right - left) // 2
旋转数组：必有一半有序，判断后排除
峰值查找：爬坡法，nums[mid] vs nums[mid+1] 决定方向
二分不限于有序数组，关键是搜索空间的单调性

📚 扩展阅读

《算法导论》第2章和第4章（二分查找与分治）
二分查找专题：LeetCode 二分查找标签
"二分答案"技巧：将优化问题转化为判定问题

思考题：如何用二分查找找到"满足某条件的最小值"？（即二分答案）例如：分割数组的最大值（LC 410），如何将"最小化最大值"转化为二分查找问题？提示：判定"最大值 ≤ mid 是否可行"具有单调性。