前言

在昨天的文章中，我們舉例的訂單資料設定為「已經照建立時間排好」，但整篇文章卻沒有提到這個特性，談到 Search 時，我們說時間複雜度是 O(N)，原因是無法從值反推位置、只能一格一格檢查，而這個結論對已經排好的陣列也成立。我們手上明明有「資料是有序的」這個額外資訊，卻沒有拿它來換取效率，這其實有點浪費（？

搜尋是個很常見的操作，例如：includes、find、indexOf 等方法，平常使用時可能不會想太多，畢竟看起來就只是找個東西而已，但搜尋的時間複雜度和資料是否已排序好很有關係，今天就來介紹這個～

一格一格找：Linear Search

先給一句話的定義：

Linear Search（線性搜尋）就是從頭開始一個一個比對，直到找到目標，或是全部看完為止。

沿用訂單的情境，這次我們手上有一批訂單資料，已經照訂單編號排好：

const orders = [1003, 1008, 1012, 1017, 1025, 1031, 1042];

現在如果我們要找編號 1025 的那一筆，會怎麼做呢？用 Linear Search 的話就是從 1003 開始往右看，一路比到第 5 個才找到。而 Linear Search 的成本會分成兩種情況，運氣最好的時候目標就是第一筆，比一次就結束，是 O(1)；運氣最差的時候有兩種可能，一種是目標落在最後一筆，另一種是目標根本不存在，這兩種都得把整批看完，所以是 O(N)。

圖 1 線性搜尋的三種情況

這兩個最壞情況雖然成本一樣，性質卻不太一樣，「目標在最後一筆」至少最後有找到，「目標不存在」則是走完全程還得回報一句找不到。後者透露的訊息是要確定一個東西不存在，比確定它存在更麻煩，因為若東西存在，運氣好第一筆就撞到了，但不存在這件事沒有任何捷徑，需要把每一筆都排除掉才能下這個結論。

這種一個一個看的搜尋，我們每天都在用：

orders.indexOf(1025); // 4
orders.findIndex((o) => o === 1025); // 4
orders.includes(1025); // true

這幾個方法的背後都是 Linear Search，這也是為什麼上一篇整理 JavaScript 陣列方法的時候，indexOf 和 includes 的時間複雜度都是 O(N)。資料量小的時候這沒有問題，7 筆訂單最多也就看 7 次，但如果今天這批訂單有一百萬筆，一格一格看就太慢了。

排序到底給了我們什麼？

現在把「已經排好」這件事拿出來用用看，假設這次要找的是 1020，還是從左邊開始一個一個比，走到 1025 的時候會發現，1025 已經比 1020 大了，而整批既然是排好的，後面的元素只會比它更大，1020 不可能躲在後面，那就不必再往下看，直接回答找不到就好。

這做法省掉的是什麼？剛才說過確定一個東西不存在沒有捷徑、非得全部看完不可，但資料排好之後捷徑就出現了，看到第一個比目標大的元素，等於一次排除掉它右邊的所有元素，這正是「未排序」和「已排序」的差別。

寫成程式如下：

function searchInSorted(items, target) {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
    if (items[i] > target) return -1; // 後面只會更大，不用看了
  }
  return -1;
}

看起來是進步了，但這樣改完之後，最壞情況真的有變好嗎？

答案是沒有，若要找的是 1042 也就是最後那一筆，還是得從頭走到底把 7 筆全部看過，若要找 1050 這個比全部都大的編號，情況也一樣，因為那句「後面只會更大」到最後一格才成立，並沒有真的提前退出，最壞情況仍然是 O(N)。這個改動只有在「目標比較小、可以早點放棄」的時候才有用，換到的是常數倍的改善，複雜度完全沒有動。

圖 2 提前放棄的兩種情境

那問題出在哪裡呢？出在我們比較的位置，從最左邊開始比，一次比較最多只能排除掉一個元素，就算運氣好一次排除掉右邊一整段，前提也是已經走了很遠。排序是個很強的性質，我們卻只把它用在「提前放棄」這種保守的地方。

從中間開始

大家應該都玩過猜數字遊戲吧～？我心裡想一個 1 到 100 之間的數，你來猜，我只會回答「太大」或「太小」，這種時候沒有人會老實地從 1 開始一個一個猜，大家都是先猜 50，因為猜完之後不管答案是太大還是太小，都能一口氣砍掉一半的可能性。

不過為什麼是先猜 50，不是先猜 30 或 80 呢？

為什麼一定要切中間？

假設不切中間、改切在 1/4 的位置，運氣好時（目標落在左邊那 1/4）只剩下 1/4，比切中間還要少，但運氣不好時會剩下 3/4，比切中間多出不少。由於衡量成本看的是最壞情況，我們真正要比的是「兩邊之中比較大的那一邊」，切在 1/4 最壞剩 3/4，切在中間則因為兩邊一樣大，最壞就是 1/2。只要切在任何不對稱的位置就一定會有一邊變大，中間是唯一讓「比較大的那一半」最小的切法。

不過嚴格說起來，切在 1/4 仍然是「每次固定砍掉一個比例」，複雜度仍然是 O(log N)，差別只在對數的底數，而 Day 02 提過 Big O 會把底數省略，兩者在 Big O 的層次上也就看不出差異。中間切法的好處落在常數上，同樣的資料量它要走的步數大約只有 1/4 切法的四成。

三種比較結果

回到訂單，如果不從最左邊開始比，改成先跟正中間那一筆比，會發生什麼事呢？把中間那一筆叫做 arr[mid]，比較之後只會有三種結果：

• arr[mid] 比目標大：目標如果存在，一定在 mid 的左邊。右半段（含 mid）整段排除。
• arr[mid] 比目標小：目標如果存在，一定在 mid 的右邊。左半段（含 mid）整段排除。
• arr[mid] 等於目標：找到了。

不論落到哪一種情況，剩下要看的範圍都只有原本的一半，接下來要做的事就是在剩下的那一半裡重複同樣的動作：找中間、比較、再砍掉一半，一直進行到找到目標，或是範圍被砍到什麼都不剩為止。

這就是 Binary Search（二元搜尋）。

Binary Search 是在一段已排序的範圍裡，反覆和中間元素比較，每次都把候選範圍縮小成一半。

逐步走一次

實際走一次流程看看～我們要在 [1003, 1008, 1012, 1017, 1025, 1031, 1042] 這批訂單裡找出 1025。這裡用三個標記來記住目前還沒被排除的範圍，left 是範圍的左端、right 是右端、mid 則是這一輪要拿來比較的中間位置，一開始 left = 0、right = 6，代表整個陣列都還是候選。

第 1 步：mid = 3、arr[3] 是 1017，因為 1017 < 1025，所以目標在右邊，把 left 移到 4，index 0 到 3 這一整段就被排除掉了。

第 2 步：範圍剩下 index 4 到 6，mid = 5、arr[5] 是 1031，這次 1031 > 1025，目標在左邊，把 right 移到 4，index 5 到 6 也整段排除。

第 3 步：範圍只剩 index 4 這一格，mid = 4、arr[4] 是 1025，找到了。

3 步就結束了。同一批資料如果用 Linear Search 要走 5 步。

圖 3 Binary Search 的逐步驟示意圖

找不到時呢？

同一批訂單，這次改找 1020 這個不存在的編號。因為 1020 和 1025 落在同一邊，前 2 步會和剛才一模一樣，範圍也是縮到只剩 index 4。到了第 3 步，mid = 4、arr[4] 是 1025，而 1025 > 1020，目標應該在左邊，right 被移到 3。這時候 left 是 4、right 是 3，left 已經跑到 right 的右邊去了，候選範圍變成空的，這就是找不到的訊號。

圖 4 找不到時：left 越過 right，範圍就空了

在 Linear Search 裡，找不到是最壞的情況，非得把每一筆都排除掉不可；但在 Binary Search 裡，找不到只不過是範圍一路縮到空為止，成本和找得到在同一個量級。

所以到底快多少？

7 筆資料看不出什麼差距，但只要把資料量放大就變明顯了，而 Binary Search 每一步都把範圍砍成一半，問題可以換個問法：一個大小是 N 的範圍，要砍幾次才會只剩下一格？

以 100 筆資料為例，每次砍掉一半的話，範圍會這樣一路縮小：

100 → 50 → 25 → 12 → 6 → 3 → 1

砍了 6 次就只剩下一格，再比最後那一格一次，總共 7 步，「100 筆資料最多要幾步」這個問題，差不多就是在問「100 要除以幾次 2 才會變成 1」。把幾種不同的資料量都算過一遍，可看出兩種搜尋的差距如下表：

同樣是一百萬筆資料，Linear Search 在最壞情況得把一百萬筆全部看完，而 Binary Search 只需要 20 步。這張表右邊那一欄的成長方式，就是 Day 02 談過的 O(log N)。當時說過它的特徵是「資料量每加倍，步數只增加 1」，表格中間幾列可以印證這件事：15 到 100 大約成長了 6 倍多，步數從 4 變成 7；10,000 到 1,000,000 成長了 100 倍，步數也只從 14 變成 20。資料量是用乘的往上跳，步數卻是用加的慢慢爬。

圖 5 兩種搜尋的成長方式

寫成程式

把前面的流程寫成實際程式如下：

function binarySearch(items, target) {
  let left = 0;
  let right = items.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);

    if (items[mid] === target) return mid; // 找到了
    if (items[mid] < target)
      left = mid + 1; // 目標在右邊，砍掉左半
    else right = mid - 1; // 目標在左邊，砍掉右半
  }

  return -1; // 範圍空了還沒找到
}

left 和 right 就是候選範圍的兩端，迴圈每跑一輪就是前面走過的一步：left 只會往右移、right 只會往左移，兩個標記一路互相靠近，直到夾住答案或交錯而過。

mid 的算法可能和直覺不太一樣：它寫成 left + Math.floor((right - left) / 2)，而不是比較直覺的 (left + right) / 2。兩者算出來的結果一樣，差別在於前者不會先把兩個 index 加起來，這件事在某些語言裡有實際的後果（和整數能表示的上限有關），JavaScript 幾乎碰不到。

這招為什麼只能用在 Array 上

「資料要先排好」真的是唯一的條件嗎？其實還有第二個前提，藏在程式碼裡一個不太顯眼的地方，就是 items[mid] 這一行。

算出 mid 之後我們直接就拿到了那一格的值，這件事看起來很理所當然。上一篇說過 Array 之所以能這樣做，是因為它的位置可以用算的，mid 是幾就直接跳過去，中間那些格子完全不需要經過。

那若換成一種「不能直接跳」的結構呢？假設資料存成一條鏈子，每一節只知道下一節在哪裡，那麼就算這條鏈子是排好序的，想拿到中間那一節還是得從頭一節一節走過去，這樣一來每一輪光是為了找到 mid 就要走掉大約 N/2 步，前面省下來的比較次數也就沒有意義了。

所以 Binary Search 能成立的前提有兩個：

• 資料已經排序，所以一次比較就能排除掉一半
• 可以直接跳到任意位置，所以「找到中間那一格」本身不用付出代價

兩個缺一不可，而 Array 剛好同時提供了它們。

為什麼是 <= 而不是 <

把 while (left <= right) 改成 while (left < right)，其他地方完全不動，然後把 7 筆訂單每一筆都拿去找一次，結果會是這樣：

1003 → 找不到
1008 → 1
1012 → 找不到
1017 → 3
1025 → 找不到     ← 這就是我們的主例
1031 → 5
1042 → 找不到

7 筆裡面有 4 筆變成找不到，其中還包括前面走了 3 步好不容易才找到的 1025。原因可以回頭看第 3 步，那時 left 和 right 都是 4、範圍剩下最後一格，而 left <= right 這個條件在 4 <= 4 的時候仍然成立，所以迴圈會再跑一輪把那一格比掉，1025 就在那裡。但如果條件寫成 left < right，4 < 4 不成立，迴圈當場結束，那一格從頭到尾沒有被檢查過。

關鍵在於 left 和 right 是閉區間的兩端，它們指到的那兩格本身也是候選，並不是站在範圍外面的界標，既然是候選，範圍縮到只剩一格（left === right）的時候就還沒結束，必須讓迴圈把那一輪跑完才行。順著同樣的邏輯，right = mid - 1 裡的那個 -1 也就有了理由，arr[mid] 這一格已經比過、確定不是目標，因此要把它排除在新範圍之外。

如果真的少寫了那個 -1，也就是把 right = mid - 1 寫成 right = mid，拿這個版本去找一個不存在的 1020，過程會變成這樣：

第 1 步   left=0  mid=3  right=6   arr[mid]=1017  →  left=4
第 2 步   left=4  mid=5  right=6   arr[mid]=1031  →  right=5
第 3 步   left=4  mid=4  right=5   arr[mid]=1025  →  right=4
第 4 步   left=4  mid=4  right=4   arr[mid]=1025  →  right=4
第 5 步   left=4  mid=4  right=4   arr[mid]=1025  →  right=4
...

從第 4 步開始就再也不動了，left、mid、right 三個全部卡在 4，範圍不再縮小，迴圈也就永遠不會結束。

圖 6 少一個 -1 的結果：範圍卡在 1 格，再也縮不下去

而這個版本最麻煩的地方在於，拿它去找 1025 是正常的，3 步就正確回傳 4，也就是說找得到的值都沒事，只有找不到的值才會出錯。

補充：left 和 right 還有另一種定義方式

right 也可以定義成「候選範圍的後面一格」，也就是它本身不是候選，這種寫法叫做半開區間（half-open interval）。那樣的話 while 條件就會變成 left < right，right 的更新也會跟著變成 right = mid。

兩種寫法都是對的，但不能混用，今天這篇一律用閉區間，left 和 right 指到的兩格都是候選。

容易漏掉的邊界

有沒有哪種輸入會讓這支程式出事呢？最常被拿出來測的是空陣列。這時候 items.length - 1 會算出 -1，於是 left = 0、right = -1，而 0 <= -1 並不成立，迴圈一次都不會跑，直接回傳 -1。這個結果是正確的，而且不需要特別加一行 if (items.length === 0) 去擋，因為空陣列本來就代表「候選範圍是空的」，閉區間寫法表達這件事的方式剛好就是 left > right，和迴圈正常跑完的結束狀態是同一個條件。left、right 和 while 條件三者的定義互相對得上，邊界自然就不需要額外處理。

憑什麼相信它是對的

現在用 Day 04 分析正確性的方法，來看看 Binary Search 為什麼是對的～

這個迴圈一路維持著什麼？

Loop invariant 要找的是一句「每一輪都成立」的話，而 Binary Search 的那句話是：

如果目標存在於陣列中，它一定還在 left 到 right 這個範圍裡。

Initialization：迴圈開始前 left = 0、right = length - 1，範圍就是整個陣列，目標如果存在，當然在裡面。

Maintenance：假設這一輪開始時這句話成立，跑完之後還成不成立呢？以 arr[mid] > target 這條路為例，我們把 right 移到 mid - 1，等於宣告「mid 和它右邊的都不可能是目標」，而這個宣告的依據就是排序：arr[mid] 右邊的每一個元素都 >= arr[mid]，arr[mid] 又已經比目標大，因此它們也全都比目標大。這裡用的是遞移律，跟一個元素比較，等於跟它後面一整串比較。

另一條路 arr[mid] < target 是它的鏡像，左半段整段排除的理由完全對稱，因此兩條路都沒有把目標弄丟，這句話在下一輪開始時仍然成立。

Termination：迴圈結束時 left > right、範圍是空的，而那句 invariant 說目標如果存在就一定在範圍裡，既然範圍已經空了，結論就是目標不存在，回傳 -1 是對的。

它一定會停嗎？

Day 04 說過，要證明一個迴圈會停，就去找一個嚴格變化而且有界的量。在 Binary Search 裡，這個量就是候選範圍的大小，也就是 right - left + 1。

每一輪不是把 left 往右移就是把 right 往左移，且因為更新時帶了 +1 和 -1，移動幅度至少是 1，範圍一定會嚴格變小，同時這個量有下界、不可能小於 0，一個嚴格遞減又有下界的量不可能一直減下去，所以迴圈一定會停。

前面那個 bug 的問題也就在這裡，right = mid 讓「範圍嚴格變小」這件事失效，當 mid 等於 right 的時候範圍根本沒有動，這個終止性論證的前提就不成立了。

資料量小的時候呢？

那以後搜尋都用 Binary Search 就好了嗎？其實不一定，還是要看資料量。7 筆資料 Linear Search 最多 7 步、Binary Search 3 步，差距只有 4 步，但 Binary Search 每一輪都要多算一次 mid、多做幾次分支判斷，這些成本在 Big O 裡會被當成常數省略掉，可是資料量小的時候，被省略掉的那一部分反而佔了大半。

還有一個上一篇提過的因素也在這裡起作用，Linear Search 是從左到右連續存取，Binary Search 則是在陣列裡跳來跳去，而連續存取通常會比跳著存取快一些，原因是 cache 一次會抓進一小段連續的記憶體，這件事也不會出現在 Big O 裡。

比較準確的說法會是，資料量夠大的時候 O(log N) 和 O(N) 的差距會大到讓其他因素都變得無關緊要。

那為什麼不是每次都先排序？

排序看起來好處多多，那是不是所有陣列都應該先排好再說？先幫這種排序好的陣列取個名字：

Ordered Array（有序陣列）是一種除了「連續存放」之外，還額外保證「元素之間維持排序」的陣列。

這是一個額外的保證，而額外的保證通常要付出成本。上一篇的表格說，插入在尾端是 O(1)、插入在中間或開頭是 O(N)，而一般的陣列想加東西，往尾端丟就好，走的正是 O(1)；但 Ordered Array 不能這樣做，新進來的訂單編號如果是 1020，它就必須被放到 1017 和 1025 中間，後面所有元素都得往右挪一格。也就是說，維持排序的代價是放棄往尾端丟這條路，每一次新增都從 O(1) 變成 O(N)。

圖 7 同一筆新訂單，兩種陣列的插入

修改也受影響，一般的陣列要改某一格的值直接寫進去就好，但 Ordered Array 改完之後還得檢查有沒有破壞排序，一旦破壞了就得把那個元素搬到正確的位置去，原本 O(1) 的一次寫入也變成 O(N)。

這是一筆取捨，用成本較高的寫入換成本較低的搜尋，值不值得取決於資料被怎麼使用。舉兩個例子來說，一份每天早上產生一次、接著被查詢一整天的商品目錄，維持排序就很值得，因為排序的成本只付一次、搜尋的好處卻收一整天；反過來，一批即時湧進來的事件記錄，寫入非常頻繁而查詢很少，那就沒有理由為了偶爾一次的查詢，讓每一次寫入都付出更高的成本。

一個小提醒

最後還有一件事比較容易被忽略，那就是 Binary Search 只能用在陣列排序所依據的那個欄位上。我們的訂單是照編號排好的，所以照編號去找可以對半砍，但如果今天要找的是「金額剛好 500 元的那筆訂單」呢？這時候就砍不動了，因為照編號排序完全不保證金額也跟著遞增。假設這 7 筆的金額依序是 180、500、260、320、90、510、240，中間那筆（編號 1017）的金額是 320，照 Binary Search 的邏輯，500 > 320 就該往右半邊找，但 500 其實躺在左邊的第 2 筆，往右找不但錯過了它，最後還會回報一句找不到。

圖 8 照金額找的情況

所以「已經排序」這句話是不完整的，完整的說法應該是「照某個欄位排序」，而 Binary Search 用不用得上，就看我們要找的是不是同一個欄位。

那若編號和金額兩種查詢都希望快呢？實務上做得到，但代價是要為金額再維護一份照金額排好的資料，用多的一份空間與維護成本，換來另一種查詢速度。

小結

小小總結一下今天對搜尋的認識～

• 為什麼需要 Binary Search？ 因為一格一格檢查在資料量大的時候太慢，而如果資料本來就排好了，這個順序本身就是一個還沒被使用的資訊。
• 用了 Binary Search 之後差在哪？ 每一次比較從「排除一個」變成「排除一半」，一百萬筆資料最多 20 步就有答案；代價是資料必須先排好，而維持排序會讓插入的成本變高。
• Binary Search 到底是什麼？ 在一段已排序的範圍裡反覆和中間元素比較，用比較結果排除掉不可能的那一半，直到找到目標或範圍變空。

最後補充幾點～

• 它需要能直接跳到中間那一格，靠的是 Array 的 random access，換成不能直接跳的結構，光找中間就會把省下來的成本抵銷掉。
• 「已經排序」講完整是「照某個欄位排序」，拿另一個欄位去找就砍不動了。
• 資料量小的時候不一定比較快，每一輪多算的 mid 與多做的分支判斷，在那個規模下佔的比重反而不低。

圖表說明：本文圖表由作者整理，並使用 Claude Code 協助繪製；內容與數據由作者確認。

Reference

• Master the Coding Interview: Data Structures + Algorithms
• 《A Common-Sense Guide to Data Structures and Algorithms, Second Edition》
• 台大林軒田教授：Data Structures and Algorithms
• Cornell CS 2112：Loop Invariants