二分查找的边界问题与变形

一、问题描述

二分查找是基础的查找算法，但实际面试中常考察其边界处理的变形问题。经典二分查找要求数组有序且无重复元素，但实际问题中经常遇到：

1. 存在重复元素时查找第一个/最后一个匹配位置
2. 查找第一个大于等于目标值的位置
3. 查找最后一个小于等于目标值的位置
4. 在旋转有序数组中查找

这些变形问题的关键在于理解搜索区间的定义和循环不变量的维护。

二、标准二分查找回顾

先回顾标准二分查找实现：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # 闭区间[left, right]
    
    while left <= right:  # 区间有效时继续
        mid = left + (right - left) // 2  # 防止溢出
        
        if arr[mid] == target:
            return mid  # 找到目标
        elif arr[mid] < target:
            left = mid + 1  # 目标在右半区
        else:  # arr[mid] > target
            right = mid - 1  # 目标在左半区
    
    return -1  # 未找到

循环不变量：在循环的每一步，目标值一定在区间[left, right]内（如果存在）。

三、查找第一个等于目标值的位置

当数组有重复元素时，标准二分查找找到的是任意一个匹配位置，不一定是第一个。

解题思路

需要在找到目标值后，继续向左搜索，判断左边是否还有相同的值。

def first_equal(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            # 关键：检查是否是第一个
            if mid == 0 or arr[mid - 1] != target:
                return mid
            else:
                # 不是第一个，继续向左搜索
                right = mid - 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

关键点分析：

1. mid == 0：已经到数组最左端，肯定是第一个
2. arr[mid - 1] != target：前一个元素不同，当前是第一个
3. 否则说明左边还有相同元素，将right设为mid-1继续向左搜索

四、查找最后一个等于目标值的位置

对称地，可以查找最后一个匹配位置。

def last_equal(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            # 关键：检查是否是最后一个
            if mid == len(arr) - 1 or arr[mid + 1] != target:
                return mid
            else:
                # 不是最后一个，继续向右搜索
                left = mid + 1
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

五、查找第一个大于等于目标值的位置（lower_bound）

这是C++ STL中lower_bound的功能，也是最常用的二分查找变形。

def lower_bound(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:  # arr[mid] >= target
            # 关键：mid可能是第一个>=target的位置
            if mid == 0 or arr[mid - 1] < target:
                return mid
            else:
                right = mid - 1  # 继续向左搜索
    
    return len(arr)  # 如果target比所有元素都大

逻辑解析：

1. 当arr[mid] >= target时，mid位置满足条件，但可能不是第一个
2. 检查mid-1位置：如果arr[mid-1] < target，则mid是第一个
3. 否则继续向左搜索

六、查找最后一个小于等于目标值的位置

def last_less_equal(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:
            # 关键：mid可能是最后一个<=target的位置
            if mid == len(arr) - 1 or arr[mid + 1] > target:
                return mid
            else:
                left = mid + 1  # 继续向右搜索
        else:  # arr[mid] > target
            right = mid - 1
    
    return -1  # 如果target比所有元素都小

七、在旋转有序数组中查找

假设原数组有序，但在某个位置旋转了，例如：[4,5,6,7,0,1,2]。

解题思路

关键观察：旋转后数组由两个有序部分组成。通过比较arr[mid]和arr[left]可以判断mid在哪个部分。

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        
        # 判断mid在左半部分还是右半部分
        if arr[left] <= arr[mid]:  # 左半部分有序
            if arr[left] <= target < arr[mid]:
                right = mid - 1  # 目标在有序的左半部分
            else:
                left = mid + 1  # 目标在右半部分
        else:  # 右半部分有序
            if arr[mid] < target <= arr[right]:
                left = mid + 1  # 目标在有序的右半部分
            else:
                right = mid - 1
    
    return -1

分情况讨论：

1. 如果arr[left] <= arr[mid]，说明左半部分有序
   • 如果目标在左半部分的范围内，就在左半部分搜索
   • 否则在右半部分搜索
2. 如果左半部分无序，那么右半部分一定有序
   • 如果目标在右半部分的范围内，就在右半部分搜索
   • 否则在左半部分搜索

八、总结与要点

1. 区间定义统一：建议始终使用闭区间[left, right]，循环条件为left <= right
2. 防止溢出：使用mid = left + (right - left) // 2而不是(left + right) // 2
3. 循环不变量：明确每一步循环中，目标值（或满足条件的值）在搜索区间内
4. 边界检查：访问mid-1或mid+1前，先检查是否越界
5. 对称性：第一个/最后一个、大于等于/小于等于等问题是对称的
6. 返回值含义：明确返回值表示什么（位置、索引、不存在时的特殊值）

掌握这些变形问题的解法，能解决大多数二分查找相关的面试问题。关键在于理解问题的本质，而不仅仅是记忆代码模板。