[algorithms] Searching 搜尋演算法

視覺化概覽

flowchart TD
    A["開始：搜尋 target"] --> B["計算 mid = left + right / 2"]
    B --> C{"arr[mid] == target?"}
    C -->|"是"| D["找到！回傳 mid"]
    C -->|"否"| E{"arr[mid] < target?"}
    E -->|"是：target 在右半"| F["left = mid + 1"]
    E -->|"否：target 在左半"| G["right = mid - 1"]
    F --> H{"left <= right?"}
    G --> H
    H -->|"是"| B
    H -->|"否"| I["找不到，回傳 -1"]

💡 白話版：想像你在一本字典裡找一個字。你可以從第一頁翻到最後一頁（Linear Search），也可以直接翻到中間然後判斷要往前還是往後（Binary Search）。

概覽

演算法	時間複雜度	前提條件
Linear Search	O(n)	無
Binary Search	O(log n)	必須已排序

Linear Search 線性搜尋

從頭到尾，一個一個找。

找 7:
[1, 3, 5, 7, 9]
 ↑        找到！
 檢查 1, 3, 5, 7

程式碼

int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

特點

• 簡單直觀
• 不需要排序
• 資料量大時很慢

Binary Search 二分搜尋

每次砍半，快速縮小範圍。

前提：陣列必須已排序！

找 7:
[1, 3, 5, 7, 9, 11, 13]
          ↑ mid=7, 找到！

找 3:
[1, 3, 5, 7, 9, 11, 13]
          ↑ mid=7, 3<7 往左找
[1, 3, 5]
    ↑ mid=3, 找到！

程式碼

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 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;
}

圖解

找 11:
Step 1: [1, 3, 5, 7, 9, 11, 13, 15, 17]
         L           M              R
         mid=9, 11>9 → 往右找

Step 2: [1, 3, 5, 7, 9, 11, 13, 15, 17]
                       L    M       R
         mid=13, 11<13 → 往左找

Step 3: [1, 3, 5, 7, 9, 11, 13, 15, 17]
                       LMR
         mid=11, 找到！

只用了 3 次！

時間複雜度比較

n（資料量）	Linear O(n)	Binary O(log n)
10	10 次	4 次
100	100 次	7 次
1,000	1,000 次	10 次
1,000,000	1,000,000 次	20 次

Binary Search 在大資料量時優勢明顯！

重要細節

1. 避免溢位

// 錯誤：可能溢位
int mid = (left + right) / 2;
 
// 正確
int mid = left + (right - left) / 2;

2. 邊界條件

// 常見錯誤
while (left < right)   // 可能漏掉 left == right 的情況
 
// 正確
while (left <= right)

3. 更新邊界

// 找到中間值後
left = mid + 1;   // 不是 mid，避免無窮迴圈
right = mid - 1;  // 不是 mid

變體應用

Lower Bound

找第一個 >= target 的位置：

int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

應用場景

• 在排序陣列中找插入位置
• 找第一個/最後一個符合條件的元素
• 範圍查詢

什麼時候用哪個？

用 Linear Search：

• 資料量小（< 100）
• 資料沒排序
• 只需要找一次

用 Binary Search：

• 資料已排序
• 需要多次搜尋
• 資料量大

相關檔案

• Java 實作：Searching.java
• 視覺化：searching.html