二分查找

1. 问题描述和示例

问题定义

给定一个按照升序排列的整数数组 nums，和一个目标值 target。请你在数组中找到 target 的索引位置，如果不存在则返回 -1。

示例

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

示例 3:
输入: nums = [5], target = 5
输出: 0

2. 核心难点分析

主要难点

1. 边界处理：正确处理 left 和 right 指针的边界条件
2. 循环不变量：保持搜索区间的一致性定义
3. 整数溢出：计算中点时避免 (left + right) / 2 的溢出问题
4. 终止条件：确定何时结束搜索循环
5. 区间定义：明确搜索区间是左闭右闭还是左闭右开

关键概念

• 搜索区间：明确定义搜索的有效范围
• 循环不变量：每次循环都要保持的条件
• 中点计算：使用 left + (right - left) / 2 避免溢出

3. 多种解法对比

3.1 递归实现

def binary_search_recursive(nums, target, left=0, right=None):
    if right is None:
        right = len(nums) - 1
    
    if left > right:
        return -1
    
    mid = left + (right - left) // 2
    
    if nums[mid] == target:
        return mid
    elif nums[mid] > target:
        return binary_search_recursive(nums, target, left, mid - 1)
    else:
        return binary_search_recursive(nums, target, mid + 1, right)

3.2 迭代实现（标准版本）

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

3.3 左边界查找

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

3.4 右边界查找

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

4. 详细代码实现

Java 实现

public class BinarySearch {
    // 标准二分查找
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return -1;
    }
    
    // 查找左边界
    public int searchLeftBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return (left < nums.length && nums[left] == target) ? left : -1;
    }
    
    // 查找右边界
    public int searchRightBound(int[] nums, int target) {
        int left = 0, right = nums.length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return (left > 0 && nums[left - 1] == target) ? left - 1 : -1;
    }
}

Python 实现

class BinarySearch:
    def search(self, nums, target):
        """标准二分查找"""
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return -1
    
    def search_left_bound(self, nums, target):
        """查找左边界"""
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return left if left < len(nums) and nums[left] == target else -1
    
    def search_right_bound(self, nums, target):
        """查找右边界"""
        left, right = 0, len(nums)
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        
        return left - 1 if left > 0 and nums[left - 1] == target else -1

5. 复杂度分析

时间复杂度

• 标准二分查找：O(log n)
• 递归实现：O(log n)
• 左/右边界查找：O(log n)

空间复杂度

• 迭代实现：O(1)
• 递归实现：O(log n) - 递归调用栈的深度

复杂度解释

每次查找都会将搜索范围缩小一半，因此最多需要 log₂n 次比较就能找到目标元素或确定元素不存在。

6. 边界情况处理

常见边界情况

1. 空数组：nums = []
2. 单元素数组：nums = [1]
3. 目标值不存在：target 不在数组中
4. 目标值在边界：target 是数组的第一个或最后一个元素
5. 重复元素：数组中有多个相同的目标值

测试用例

def test_binary_search():
    bs = BinarySearch()
    
    # 测试空数组
    assert bs.search([], 1) == -1
    
    # 测试单元素
    assert bs.search([1], 1) == 0
    assert bs.search([1], 2) == -1
    
    # 测试目标在边界
    assert bs.search([1, 2, 3, 4, 5], 1) == 0
    assert bs.search([1, 2, 3, 4, 5], 5) == 4
    
    # 测试目标不存在
    assert bs.search([1, 3, 5, 7, 9], 4) == -1
    
    # 测试重复元素
    nums = [1, 2, 2, 2, 3]
    assert bs.search_left_bound(nums, 2) == 1
    assert bs.search_right_bound(nums, 2) == 3

7. 相关变种问题

7.1 搜索旋转排序数组

def search_rotated_array(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # 判断哪一半是有序的
        if nums[left] <= nums[mid]:  # 左半部分有序
            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

7.2 寻找峰值

def find_peak_element(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    
    return left

7.3 搜索插入位置

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

8. 性能优化技巧

8.1 避免整数溢出

# 错误的写法（可能溢出）
mid = (left + right) // 2

# 正确的写法
mid = left + (right - left) // 2

8.2 减少比较次数

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

8.3 缓存友好的实现

对于大数组，可以考虑使用插值搜索或指数搜索来提高缓存命中率。

9. 实际应用场景

9.1 数据库索引

• B树和B+树索引的核心就是二分查找思想
• 用于快速定位数据记录

9.2 系统设计

• 负载均衡：在服务器列表中查找合适的服务器
• 缓存系统：在有序的缓存键中查找数据
• 版本控制：在版本历史中查找特定版本

9.3 算法优化

• 排序算法：归并排序中的合并操作
• 动态规划：在状态空间中搜索最优解

9.4 实际代码示例

# 在日志文件中按时间戳查找
def find_log_by_timestamp(logs, target_time):
    left, right = 0, len(logs) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        log_time = logs[mid]['timestamp']
        
        if log_time == target_time:
            return mid
        elif log_time > target_time:
            right = mid - 1
        else:
            left = mid + 1
    
    return -1

10. 面试要点总结

10.1 常见考点

1. 基础实现：能够快速写出标准的二分查找代码
2. 边界处理：正确处理各种边界情况
3. 变种问题：掌握左边界、右边界查找
4. 复杂度分析：能够分析时间和空间复杂度
5. 实际应用：了解二分查找在实际项目中的应用

10.2 面试技巧

1. 明确区间定义：在开始编码前明确搜索区间是左闭右闭还是左闭右开
2. 保持循环不变量：确保每次循环都保持相同的区间定义
3. 测试边界情况：主动提及并测试各种边界情况
4. 优化细节：提到避免整数溢出等优化技巧

10.3 回答模板

1. 问题理解：确认数组是否有序，是否有重复元素
2. 算法选择：解释为什么选择二分查找
3. 代码实现：写出清晰的代码
4. 复杂度分析：分析时间和空间复杂度
5. 边界测试：考虑各种边界情况
6. 优化讨论：提及可能的优化方向

10.4 常见错误

1. 死循环：循环条件设置错误导致无限循环
2. 边界错误：left 和 right 的更新逻辑错误
3. 整数溢出：使用 (left + right) / 2 计算中点
4. 区间混乱：左闭右闭和左闭右开区间混用

总结

二分查找是一个看似简单但细节丰富的算法。掌握二分查找需要：

1. 理解核心思想：通过不断缩小搜索范围来快速定位目标
2. 掌握多种实现：递归、迭代、边界查找等不同实现方式
3. 注意实现细节：边界处理、循环不变量、整数溢出等问题
4. 熟悉变种问题：旋转数组、峰值查找等相关问题
5. 了解实际应用：在系统设计和实际项目中的应用场景

通过大量练习和深入理解，可以在面试和实际工作中熟练运用二分查找算法。