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語法，包含標題、代碼塊、表格等元素，便于閱讀和理解。