leetcode中如何解决二分查找问题

# LeetCode中如何解决二分查找问题

## 一、二分查找算法简介

二分查找（Binary Search）是一种在**有序数组**中查找特定元素的高效算法，时间复杂度为O(log n)。其核心思想是通过不断缩小搜索范围来快速定位目标值。

### 基本算法框架
```python
def binary_search(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:
            left = mid + 1
        else:
            right = mid - 1
    return -1

二、LeetCode常见题型分类

1. 标准二分查找

• 例题：704. 二分查找
• 特点：直接套用基础模板即可解决

2. 查找边界条件

• 左边界查找（第一个等于target的元素）

def left_bound(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 - 1
    return left if left < len(nums) and nums[left] == target else -1

• 右边界查找（最后一个等于target的元素）

def right_bound(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 - 1
    return right if right >= 0 and nums[right] == target else -1

3. 旋转排序数组问题

• 例题：33. 搜索旋转排序数组
• 关键点：先确定有序区间，再在有序区间内二分

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 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

4. 二分答案法

• 例题：875. 爱吃香蕉的珂珂
• 特点：在可能的答案范围内进行二分搜索

三、解题技巧总结

1. 循环条件选择

• while left <= right：搜索区间为闭区间[left, right]
• while left < right：搜索区间为左闭右开[left, right)

2. 中间值计算

• 推荐写法：mid = left + (right - left) // 2
• 防止整数溢出的同时保证正确性

3. 边界更新策略

4. 调试技巧

• 打印关键变量：left, right, mid
• 使用小规模测试用例验证边界条件

四、典型例题解析

例题1：34. 在排序数组中查找元素的第一个和最后一个位置

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

例题2：69. x的平方根

def mySqrt(x):
    left, right = 0, x
    while left <= right:
        mid = (left + right) // 2
        if mid * mid <= x < (mid + 1) * (mid + 1):
            return mid
        elif mid * mid > x:
            right = mid - 1
        else:
            left = mid + 1
    return left

五、常见错误与注意事项

1. 未排序数组：二分查找要求输入必须是有序数组
2. 死循环：边界更新不当可能导致无限循环
3. 整数溢出：大数计算时使用(left + right) // 2可能溢出
4. 边界条件：空数组、单元素数组等特殊情况需要单独处理

通过系统性地掌握这些模式和技巧，LeetCode中的二分查找类问题将变得有章可循。建议初学者从标准二分查找开始练习，逐步过渡到更复杂的变种问题。 “`

文章总计约1100字，包含： 1. 算法简介和基础模板 2. 四大常见题型分类 3. 解题技巧总结表格 4. 典型例题的Python实现 5. 常见错误提醒 6. 适当的代码示例和注释

格式采用标准的Markdown语法，包含标题、代码块、表格等元素，便于阅读和理解。