当然！以下是《我爱学算法之—— 二分查找（中）》的详细讲解，适合已经掌握二分查找基础的你，深入理解进阶技巧与变种应用。

📚 我爱学算法之—— 二分查找（中）

二分查找的进阶技巧与变种应用解析

目录

  1. 二分查找复习（基础回顾）
  2. 二分查找的常见变体
  3. “左边界”和“右边界”二分查找
  4. 应用案例讲解
  5. 编写模板代码与调试技巧
  6. 二分查找中常见陷阱及规避方法
  7. 拓展：答案二分与参数二分
  8. 经典题目推荐及解题思路

1️⃣ 二分查找复习（基础回顾）

  • 定义：在一个有序数组里，通过不断折半区间范围，快速定位目标元素或其位置。
  • 时间复杂度：O(log n)
  • 基础实现：
def binary_search(arr, target):
    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

2️⃣ 二分查找的常见变体

  • 查找左边界（第一个等于 target 的位置）
  • 查找右边界（最后一个等于 target 的位置）
  • 查找第一个大于等于 target 的位置
  • 查找最后一个小于等于 target 的位置

3️⃣ 左边界和右边界二分查找

查找左边界

目标：找到数组中第一个等于 target 的元素索引。

def left_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

查找右边界

目标：找到数组中最后一个等于 target 的元素索引。

def right_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left - 1

4️⃣ 应用案例讲解

案例 1：查找目标元素出现的区间

def search_range(nums, target):
    left = left_bound(nums, target)
    right = right_bound(nums, target)
    if left <= right and right < len(nums) and nums[left] == target and nums[right] == target:
        return [left, right]
    return [-1, -1]

5️⃣ 编写模板代码与调试技巧

  • 使用 while left < right 来避免死循环
  • 注意区间的开闭：[left, right) 或 [left, right]，要保持统一
  • 在调试时，打印 left, mid, right 变量，辅助理解循环过程
  • 边界判断时，注意数组越界和空数组情况

6️⃣ 常见陷阱及规避方法

问题解决建议
死循环保证循环条件收敛，区间移动正确
边界条件出错明确区间开闭，使用统一写法
返回值错误结合数组长度判断，防止越界
找不到目标时误判明确检查返回索引对应元素是否为目标

7️⃣ 拓展：答案二分与参数二分

  • 答案二分：用二分查找来确定结果的数值范围，如找最小满足条件的值。
  • 参数二分：二分查找应用在解题条件或判定函数上，而非数组索引。

8️⃣ 经典题目推荐及解题思路

题号题目名称思路点
33搜索旋转排序数组二分查找+区间划分判断
34在排序数组中查找元素的第一个和最后一个位置左右边界二分查找
69x 的平方根答案二分
153寻找旋转排序数组中的最小值利用二分查找确定区间变化点
278第一个错误的版本参数二分

总结

二分查找不仅是查找目标值这么简单，理解区间划分、边界处理、变形应用是进阶的关键。掌握这些，能极大提升解决搜索类问题的效率和准确度。