Terry Yao's Blog

algorithmsSearching 搜尋演算法
algorithms

Searching 搜尋演算法

閱讀時間約 9 分鐘

cover

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

先講結論

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

演算法時間複雜度前提條件
Linear SearchO(n)無
Binary SearchO(log n)必須已排序
Jump SearchO(√n)必須已排序
Interpolation SearchO(log log n) 平均、O(n) 最壞已排序且數值分布均勻

後面兩個是 Binary Search 的旁支親戚，工作上幾乎用不到，但各自打破了二分的一個隱藏假設——Jump 不靠「隨機跳中點」，Interpolation 不砍正中間。看懂它們，你對「砍一半」的理解會更完整一點。

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)
100100 次7 次
1,000,0001,000,000 次20 次

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

Jump Search：往前跳，別回頭

Binary Search 有個隱藏前提：跳到任何一格的成本都一樣。陣列成立，arr[mid] 一個加法就到。但資料躺在連結串列上時就破功了——要跳到中點，你得從頭一格一格走過去，「跳中點」的優勢等於沒有。

Jump Search 就是為這種場景設計的：固定步長 √n 往前跳，跳過頭了退回上一個區塊線性掃描。全程只往前、不回頭，不需要「隨機跳到任意一格」這個能力。

找 13，n=9，步長 √9 = 3：
[1, 3, 5, 7, 9, 11, 13, 15, 17]
        ↑ index 2 (值 5)，5<13 繼續跳
                 ↑ index 5 (值 11)，11<13 繼續跳
                          ↑ index 8 (值 17)，17≥13 停，退回上一區塊
        區塊 [6,7,8] 內線性掃：13 在 index 6，找到！
int jumpSearch(int[] arr, int target) {
    int n = arr.length;
    if (n == 0) return -1;
    int step = (int) Math.floor(Math.sqrt(n));
    if (step < 1) step = 1;
 
    int prev = 0;
    while (arr[Math.min(step, n) - 1] < target) {   // 跳到「區塊尾端 >= target」
        prev = step;
        step += (int) Math.floor(Math.sqrt(n));
        if (prev >= n) return -1;
    }
    while (prev < Math.min(step, n)) {              // 區塊內線性掃
        if (arr[prev] == target) return prev;
        prev++;
    }
    return -1;
}

步長為什麼偏偏是 √n？因為「往前跳幾次」和「最後在區塊裡掃幾格」是一組蹺蹺板——步長越大跳得越少但掃得越多，反之亦然，兩邊在 √n 交會，總和最小。這種「兩個成本此消彼長、取平方根平衡」的手法，之後你在分塊、在莫隊算法還會一再遇到，先在這裡認個臉。

Interpolation Search：像查電話簿那樣猜

在紙本電話簿找「王先生」，你不會從正中間翻起，而是直接往後段翻——因為「王」的筆畫排在後面。Interpolation Search 就是把這個直覺寫成公式：不固定取中點，而是照 target 在值域裡的比例去估它大概落在哪。Binary Search 每次都砍正中間，Interpolation 則會依比例跳到它「猜」的位置。

找 70，值域 [10..90]：
[10, 20, 30, 40, 50, 60, 70, 80, 90]
pos = lo + (70-10)/(90-10) × (8-0) = 6
                                     ↑ index 6 剛好是 70，一步命中
（Binary 會先取 index 4=50，還得再找一次）
int interpolationSearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        if (lo == hi) return arr[lo] == target ? lo : -1;
        if (arr[hi] == arr[lo]) return arr[lo] == target ? lo : -1;  // 擋除以 0
        int pos = lo + (int) (((long) (target - arr[lo]) * (hi - lo)) / (arr[hi] - arr[lo]));
        if (arr[pos] == target) return pos;
        if (arr[pos] < target) lo = pos + 1;
        else hi = pos - 1;
    }
    return -1;
}

值分布均勻時它平均只要 O(log log n)，比 Binary 還快。但天下沒有白吃的午餐——分母 arr[hi] - arr[lo] 在「一堆相同值」時會變 0，少了 arr[hi] == arr[lo] 那道守衛，[5,5,5,5] 找 5 直接噴 ArithmeticException。而且資料分布一不均勻（像指數成長），它就退化到 O(n)。均勻數值資料上是神，其他場合是雷。

看一下四個放在一起的差距：

n（資料量）Linear O(n)Binary O(log n)Jump O(√n)Interpolation＊
100100 次7 次10 次~3 次
1,000,0001,000,000 次20 次1,000 次~4 次

＊Interpolation 為「分布均勻」的平均值；不均勻時退化到接近 Linear。

🎬 互動視覺化：四種搜尋並排同步對比 — 同一組資料、同一個 target，即時看 Linear / Binary / Jump / Interpolation 各自比了幾次。

三個會害你 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，請去買樂透。

接下來往哪走

關係圖譜

反向連結