[algorithms] Searching 搜尋演算法

搜尋就兩招：笨笨從頭找，或聰明地砍半。差別是百萬筆資料時，一個找一百萬次，一個只要二十次。

先講結論

Binary Search 在已排序的資料上是無敵的。但如果你的資料沒排序、量又小，Linear Search 反而是正解。別為了炫技在 10 筆資料上搞二分搜尋，那只是在浪費你同事的耐心。

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

Linear Search：最老實的方法

從頭到尾，一個一個比。就像你在一疊沒整理的發票裡找某一張——除了翻完，沒有捷徑。

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

什麼時候用它？資料量小（< 100）、資料沒排序、或者你只需要找一次。不丟臉，很多場景它就是最佳解。

Binary Search：每次砍一半

想像翻字典找「狗」這個字。你會從第一頁開始翻嗎？不會，你會翻到中間，發現是「雞」，「狗」在前面，所以翻前半——再砍半、再砍半。這就是 Binary Search。

前提：陣列必須已排序。沒排序就用 Binary Search 是會出事的。

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;
}

看一下它有多猛：

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

百萬筆資料，20 次就找到。這不是演算法，這是魔法。

三個會害你 debug 到半夜的坑

坑一：整數溢位。 這個 bug 藏在 Java 的 JDK 裡好幾年才被發現。

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

坑二：< 還是 <=？ 用 while (left < right) 會漏掉 left == right 的情況，也就是最後一個元素。

// 正確
while (left <= right)

坑三：更新邊界用 mid 而不是 mid ± 1。 恭喜你，無窮迴圈。

left = mid + 1;   // 不是 mid
right = mid - 1;  // 不是 mid

Lower Bound：找「第一個 >= target」的位置

這是 Binary Search 最實用的變體。在排序陣列中找插入位置、找第一個符合條件的元素，都靠它。

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;
}

注意這裡 right = mid 而不是 mid - 1，因為 mid 本身可能就是答案。Binary Search 的變體之所以難，就是這些邊界條件每次都不太一樣。我到現在還是每次都要想一下。

---

Binary Search 最大的敵人不是演算法本身，而是 off-by-one。如果你寫 Binary Search 一次就 AC，請去買樂透。