CC++ & Algorithm

Python二分查找经典问题

困难2
语言版本：C++Python
概述：二分查找经典问题包括：在有序数组中查找第一个或最后一次出现的位置、寻找插入位置、求平方根等，掌握这些能应对常见编程挑战。

二分查找经典问题全掌握：第一次、最后一次、插入位置、平方根

你学会了最基础的二分查找——在一个有序数组里快速找到某个数。但在实际编程中，会遇到很多“变种”问题：比如数组里有重复数字，你想找目标值第一个出现的位置（比如点名时第一个回答的人），或者最后一个出现的位置（比如排队时最后一位同身高的人）；又比如目标不在数组里，你想知道它应该插在哪（比如新书按书名插到书架中间）；还有求一个数的平方根（只取整数部分，比如√8≈2.828，整数部分是2）。这些问题都可以通过调整二分查找的边界条件来解决，而且非常重要，竞赛和面试里经常考。

下面我们一个个拆解，每部分都会配上代码和生活中的例子，让你一学就会。

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

场景：老师有一份按学号排好的名单，里面可能有同名同姓的同学。她想知道“张三”这个名字第一次出现在第几个位置（从0开始数）。
思路：用二分查找。当找到目标时，不立刻返回，而是继续往左边找，因为左边可能还有更早的相同值。直到左指针超过右指针，最后记录的 ans 就是第一个位置；如果没找到过，ans 保持 -1。

def first_occurrence(arr, target):
    left, right = 0, len(arr) - 1   # 左指针，右指针
    ans = -1                        # 默认没找到
    while left <= right:
        mid = (left + right) // 2   # 中间位置
        if arr[mid] == target:      
            ans = mid               # 先记录这个位置
            right = mid - 1         # 继续向左边找，看有没有更早的
        elif arr[mid] < target:     # 目标在右边
            left = mid + 1
        else:                       # 目标在左边
            right = mid - 1
    return ans

测试：

nums = [1, 2, 2, 2, 3, 4]          # 有序数组，有重复的2
print(first_occurrence(nums, 2))  # 输出 1（索引1是第一个2）

生活类比：比如班级队列按身高从矮到高排好，里面有多个同样高的人。你想知道第一个身高160厘米的同学站第几个位置。用二分查找时，即使中间遇到了一个160厘米的，你还要继续往左边看，看看前面还有没有更早的160厘米。

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

场景：还是那个有重复名字的名单，老师想知道最后一个叫“张三”的是第几个。
思路：找到目标后，不返回，继续往右边找，因为右边可能有更靠后的相同值。直到循环结束，返回最后记录的 ans。

def last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            ans = mid               # 记录这个位置
            left = mid + 1          # 继续向右边找，看有没有更晚的
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans

print(last_occurrence(nums, 2))  # 输出 3（索引3是最后一个2）

注意：和第一个位置比，这里移动的是左指针，因为要继续向右探索。

生活类比：排队时，你发现队伍里好几个人穿着同样的校服。你想找到最后一个穿这种校服的人。先用二分找到中间一个，然后继续往后看，直到超出队伍末尾。

3. 查找插入位置（目标不在数组中时）

场景：你有一本新书《Python入门》，想到书架上按拼音把书插进去。书架上的书已经按书名字母排好了。你要找到新书应该插在哪两本书之间。
思路：使用二分查找，如果目标值存在则返回它的索引；如果不存在，返回它应该被插入的位置（第一个大于目标值的位置）。这其实就是 Python 内置模块 bisect 里的 bisect_left 功能。本质上，用 left 指针的最终值就是插入位置。

def search_insert_position(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid          # 找到了，直接返回位置
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left                 # 没找到，left 就是插入位置

测试：

nums = [1, 3, 5, 6]
print(search_insert_position(nums, 5))   # 输出 2（5的索引是2）
print(search_insert_position(nums, 2))   # 输出 1（2应插在索引1处，即1后面）
print(search_insert_position(nums, 7))   # 输出 4（7应插在最后）

生活类比：假设你有一排按年龄排好的小朋友（年龄从小到大）。老师要插入一个年龄为10岁的新同学，如果已经有10岁的小朋友，他就站在那个位置；如果没有，他就站在第一个大于10岁的小朋友前面（也就是比他小的所有人的后面）。

提示：这个函数与前面 first_occurrence 的区别在于，当目标不存在时，它返回插入位置而不是 -1。如果你想要更精确的“第一个等于目标值的位置”并且目标不存在时返回插入位置，可以直接写 return left，这就是 bisect_left 的实现。

4. 求平方根（整数部分）

场景：计算 sqrt(8)，结果大约是2.828，整数部分是2。如何不用数学库函数，只靠二分查找得到整数平方根？
思路：在范围 [0, x] 内找一个最大整数 k，使得 k*k <= x。这就是典型的“二分答案”思想。你猜一个数 mid，如果 mid*mid <= x，说明答案可能还更大，尝试右边；否则说明太大，往左边找。

def my_sqrt(x):
    if x < 0:                # 处理负数（一般不考虑）
        return -1
    left, right = 0, x       # 注意：x可能为0
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if mid * mid <= x:
            ans = mid         # 记录这个可能的答案
            left = mid + 1    # 试着往更大的数找
        else:
            right = mid - 1   # 太大了，往小找
    return ans

print(my_sqrt(8))   # 输出 2
print(my_sqrt(16))  # 输出 4
print(my_sqrt(0))   # 输出 0

生活类比：你有一块正方形地毯，面积是8平方米。你想知道它的边长最大是多少（整数米）。先猜4米，4×4=16>8，太大了；改猜2米，2×2=4≤8，可行；再猜3米，3×3=9>8，所以答案就是2米。

小技巧：如果 x 很大（比如 10^9），mid*mid 可能会溢出（Python 不存在整数溢出，但其他语言要注意）。实际面试题中常用 mid <= x//mid 代替乘法。

常见错误（新手最容易踩的坑）

  1. 死循环：当 left 和 right 相邻时，mid 可能等于 left，如果条件写错，left 或 right 不更新，就会无限循环。比如 left = mid 而不是 mid+1。
    正确做法：在条件分支中，每次移动指针都加或减1，不要写 left = mid。

  2. 边界条件混淆：用 while left <= right 还是 while left < right？如果你用 <=，最后 left 会超过 right，适合记录答案的情况；如果你用 <，循环结束时 left == right，适合返回 left 是插入位置的情况。建议统一用 <=，逻辑更清晰。

  3. 忘记更新 ans：在求第一个/最后一个位置时，如果找到了目标，必须记录 ans，否则最后返回 -1（除非你直接返回 left）。

  4. 数组为空：如果 arr = []，len(arr)-1 是 -1，循环直接跳过，ans 保持 -1，结果正确。但在其他变种中要小心，比如 search_insert_position 里 left=0 会返回0，也是合理的。

  5. 平方根中 x 为 0 或 1：my_sqrt(0) 和 my_sqrt(1) 都能正确处理，因为 mid*mid <= x 在 0 和 1 时都会记录。

完整可运行的示例

下面把所有功能集成在一个 Python 文件中，方便你运行测试。

# 二分查找经典变种完整示例

def first_occurrence(arr, target):
    """返回第一个等于 target 的位置，没找到返回 -1"""
    left, right = 0, len(arr) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            ans = mid
            right = mid - 1          # 继续左边
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans

def last_occurrence(arr, target):
    """返回最后一个等于 target 的位置，没找到返回 -1"""
    left, right = 0, len(arr) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            ans = mid
            left = mid + 1           # 继续右边
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return ans

def search_insert_position(arr, target):
    """返回 target 应插入的位置（第一个大于或等于 target 的位置）"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left   # 没找到，返回插入点

def my_sqrt(x):
    """返回 x 的平方根的整数部分（x >= 0）"""
    if x < 0:
        return -1
    left, right = 0, x
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if mid * mid <= x:
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
    return ans

# 测试
if __name__ == "__main__":
    test_arr = [1, 2, 2, 2, 3, 4, 5]
    print("数组:", test_arr)
    print("第一个2的位置:", first_occurrence(test_arr, 2))   # 1
    print("最后一个2的位置:", last_occurrence(test_arr, 2))  # 3
    print("插入2的位置:", search_insert_position(test_arr, 2))  # 1 (已有)
    print("插入6的位置:", search_insert_position(test_arr, 6))  # 7 (后面)
    print("平方根(8):", my_sqrt(8))    # 2
    print("平方根(16):", my_sqrt(16))  # 4
    print("平方根(0):", my_sqrt(0))    # 0

相关指引

  • 如果你觉得这些变种还不够，可以继续学习 二分查找在旋转有序数组中的应用（比如 [4,5,6,1,2,3] 中找目标），那是更高级的变种。
  • 二分查找的思想还可以用来解决 最优化问题，比如“在给定时间内最多能完成多少任务”、“最小化最大值”等，这类问题常与贪心或搜索结合。
  • 想更深入掌握，推荐练习 LeetCode 34（在排序数组中查找元素的第一个和最后一个位置）、LeetCode 35（搜索插入位置）、LeetCode 69（x 的平方根）。

多练习，你会发现所有二分变种都围绕着“调整指针移动方向”和“记录答案”这两个核心。加油！

例题精讲

1单选题

在有序数组nums中查找目标值target第一次出现的位置，采用二分查找时，当nums[mid] == target，正确的处理是？

A直接返回mid
B令right = mid - 1
C令left = mid + 1
D令right = mid
2判断题

二分查找只能应用于有序数组，且数组必须为升序排列。

3填空题
实现函数search_insert(nums, target)，返回target应该插入的位置（即第一个大于等于target的位置）。请补全代码。
def search_insert(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            ___
    return left
4单选题

使用二分查找求非负整数x的平方根（向下取整），在整数范围[0, x]内进行二分，判断条件应为以下哪一个？

Amid * mid <= x
Bmid * mid < x
Cmid * mid >= x
Dmid * mid > x
5填空题
查找有序数组中最后一个等于target的位置，若不存在返回-1。请补全代码。
def last_occurrence(nums, target):
    left, right = 0, len(nums) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            ans = mid
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            ___
    return ans