二分搜尋演算法完全指南#

二分搜尋（Binary Search）是程式設計中最基礎也最重要的演算法之一。雖然概念簡單，但要寫出正確且高效的實作卻不容易。

什麼是二分搜尋？#

二分搜尋是一種在已排序陣列中尋找特定元素的演算法。它的核心思想是：

檢查中間元素
如果中間元素就是目標，返回位置
如果目標小於中間元素，在左半部分繼續搜尋
如果目標大於中間元素，在右半部分繼續搜尋

時間複雜度#

時間複雜度：O(log n)
空間複雜度：O(1)（迭代版本）

每次搜尋都能排除一半的元素，所以效率非常高！

基本實作#

Python 版本#

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 避免溢位
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1  # 找不到

C++ 版本#

#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

常見陷阱與注意事項#

1. 中點計算#

❌ 錯誤寫法：mid = (left + right) / 2 ✅ 正確寫法：mid = left + (right - left) / 2

原因：避免整數溢位問題。

2. 邊界條件#

使用 left <= right 而不是 left < right
正確更新 left = mid + 1 和 right = mid - 1

3. 陣列必須已排序#

二分搜尋只能用於已排序的陣列！

變形應用#

1. 尋找第一個出現位置#

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 繼續往左找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

2. 尋找插入位置#

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