二分查找算法详解与力扣实战技巧

1. 二分查找算法基础与力扣实战指南

二分查找（Binary Search）是计算机科学中最经典且高效的搜索算法之一，尤其适合处理有序数据集。我在力扣（LeetCode）平台上刷题时发现，掌握二分查找的变体应用能解决近30%的中等难度算法题。这个算法看似简单，但边界条件的处理往往让新手栽跟头——我自己就曾在while循环的条件判断上反复调试过多次。

二分查找的核心思想是"分而治之"：每次比较中间元素后，都能排除一半的搜索空间。对于一个包含n个元素的有序数组，时间复杂度仅为O(log n)，相比线性搜索的O(n)显著提升。在力扣的题目设计中，二分查找不仅用于基础搜索，还衍生出旋转数组搜索、边界查找等变种题型。

关键提示：二分查找的难点不在于理解原理，而在于处理各种边界条件。比如循环终止条件应该是left < right还是left <= right？mid计算应该向上还是向下取整？这些细节会直接影响代码的正确性。

2. 标准二分查找实现与力扣704题解析

2.1 基础模板代码实现

我们先看力扣第704题"二分查找"的标准实现。这是最基础的版本，适合作为模板记忆：

python复制def search(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 -1

这个模板有几个关键点需要注意：

1. 循环条件使用left <= right而非<，确保能检查到最后一个元素
2. mid的计算采用left + (right - left) // 2而非(left + right) // 2，避免大数相加导致的整数溢出
3. 每次调整边界时都是mid ± 1，确保搜索范围确实在缩小

2.2 边界条件深度解析

在实际刷题中，我发现边界条件的处理最容易出错。以力扣35题"搜索插入位置"为例，题目要求返回目标值应插入的位置。这时候模板需要微调：

python复制def searchInsert(nums: List[int], target: int) -> int:
    left, right = 0, len(nums)  # 注意right初始值
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

这里的变化很微妙但很重要：

1. right初始为len(nums)而非len(nums)-1，因为插入位置可能在数组末尾
2. 循环条件变为left < right，当它们相等时就找到了插入点
3. 当nums[mid] >= target时，right直接取mid而非mid-1

3. 二分查找的四大高阶变体

3.1 旋转数组搜索（力扣33题）

旋转数组是指将有序数组的一部分移动到末尾，如[4,5,6,7,0,1,2]。搜索这类数组需要先确定有序区间：

python复制def search(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if