紀錄工作經驗、相關知識,解決技術相關問題。

工作雜談, 新手 Jamp Holes, 網站相關, 資訊相關

如何使用二分搜尋 (Binary Search) 快速排查 Bug

如何使用二分搜尋 (Binary Search) 快速排查 Bug 特色圖片

在龐大程式碼中排查 Bug 時,最直覺且高效的方法之一就是使用二分搜尋(Binary Search),尤其當你面對的是從未碰過的專案時尤為好用,能以系統化的方式快速鎖定問題根源。

什麼是二分搜尋 Binary Search?

二分搜尋 (Binary Search) 是一種常見於搜尋演算法的技術,也可以應用在除錯上,以系統化的方式快速找出錯誤點。

簡單理解, 就像你想在一塊蛋糕中, 找出一片蛋殼, 最直觀的方法, 將一塊蛋糕平均一刀切, 你先檢查左邊的, 沒問題再檢查右邊的, 如果左邊有問題呢?那左邊就再一刀切, 一直循環, 直到你找到問題。

二分搜尋除錯法的優勢

✅ 高效縮小範圍:每次測試大約排除一半需要檢查的程式碼。
✅ 系統化排查:不依賴猜測,能快速找出 Bug 根源。
✅ 適用於各種場景:不管是函式調試、UI 渲染錯誤,還是版本回溯,都能使用這種方法。

以下用 1,024 行程式碼為例,比較逐一排查與二分搜尋需要的測試次數:

比較維度傳統線性逐一排查 (Linear Search)二分搜尋 (Binary Search)
每次排除比例每次排除 1 筆/1 行 (效率固定)每次排除 50% 的剩餘範圍
1,024 行最多需要的測試次數最多 1,024 次10 次(1,024 → 512 → … → 1)
排查方式逐行檢查每次測試排除一半,再測剩下的一半
適用情境資料量極小或完全未排序的混亂狀態具備順序性、邏輯相依或版本時間序列

如何使用二分搜尋 Binary Search 排查錯誤

了解概念後,這裡就列一個簡單的範例,假設你有一個主要函式,裡面執行了多個子步驟,如下:

const main = () => {
   const a = callA()
   const b = callB()
   const c = callC()
   const d = callD()
   const e = callE()
}

在日常除錯中,除了直接將後半段程式碼註解掉之外,另一種常見且實用的技巧是利用「提早 return(Early Return)」或「二分夾擠」來中斷執行。例如,你可以直接在函式中間插入回傳值或強制結束,藉此確認錯誤是否發生在此之前:

const main = () => {
   const a = callA()
   const b = callB()
   
   // 透過提早 return 來中斷後續執行,測試前半段是否正常
   return { b }

   const c = callC()
   const d = callD()
   const e = callE()
}

搭配記錄工具來列出目前狀態與資料正確性,看是否如預期。透過「註解區塊」、「提早 return」與「二分夾擠」交替使用,反覆操作,一點一點往下排查,就能迅速收斂範圍直到找到問題點。

透過 Git Bisect 將版本歷史二分搜尋自動化

除了在單一檔案或單一函式內手動進行二分搜尋之外,當面對版本控制歷史時,若某個 Bug 是在過去某次未知 Commit 中引入的,手動逐一切換測試會耗費大量時間。此時,可以利用內建的 git bisect 指令來自動化整個流程。

git bisect 的本質就是二分搜尋演算法在版本歷史上的應用。使用時只需指定一個已知正常的 Commit(例如上次發布的標籤)與一個已知異常的 Commit(例如當前的 Head),工具就會自動切換到中間的 Commit 讓開發者進行測試:

  1. 啟動二分搜尋:輸入 git bisect start
  2. 設定異常點與正常點:
    • 標記當前異常版本:git bisect bad
    • 標記過去正常版本:git bisect good <commit-hash>
  3. 自動切換測試:系統會自動切換到中間的 Commit。此時執行測試或編譯,若該版本正常則輸入 git bisect good;若有 Bug 則輸入 git bisect bad。
  4. 重複流程:會繼續縮小一半範圍,直到精準定位到引入該 Bug 的兇手 Commit,最後輸入 git bisect reset 即可回到原本的工作分支。

此外,如果你的專案已經配置了完善的自動化測試腳本,你甚至不需要手動逐一檢查每個切換出來的版本。只要透過 git bisect run 指令,就能讓系統自動執行測試指令並根據回傳狀態自動完成二分搜尋:

git bisect run npm test

只要一行指令,系統就會在背景自動執行測試並不斷切換 Commit,瞬間找出問題 Commit,大幅省下人工介入的時間。這種方式將二分搜尋的概念從程式碼區塊延伸至時間維度,能以極高的效率完成大型專案的歷史排查。

⚠️ Git Bisect 實務防呆提示:git bisect good 與 git bisect bad 沒有指定 Commit 時,標記的是目前所在的 Commit。執行期間如果切到其他分支修 Bug,還沒切回來就輸入 good 或 bad,會標到錯的 Commit,結果跟著出錯。萬一標錯了,可以用 git bisect log > bisect.log 存下紀錄、刪掉標錯的那幾行,再執行 git bisect reset 與 git bisect replay bisect.log 重播回正確狀態(Git 官方文件:git-bisect)。

實務排錯常見雷區與案例解析

在實務開發場景中,雖然二分搜尋與 git bisect 是極為強大的排查武器,但在團隊協作與複雜專案中,經常會因為忽略某些前置條件而導致除錯翻車。

1. 非同步行為與狀態汙染導致二分夾擠失效

  • 踩坑情境:在前端或後端使用記錄工具或提早 return 進行二分夾擠時,常忽略被註解或中斷的函式其實帶有全域狀態、快取或是非同步請求相依性。
  • 實務後果:當你把後半段的執行步驟註解掉或提早回傳時,因為少了後續的非同步初始化,反而引發其他元件或型別噴出例外錯誤,導致工程師誤判該區塊本來就有 Bug。

2. git bisect 過程中遇到「中途 Commit 無法編譯」

  • 踩坑情境:在使用版本歷史二分搜尋尋找歷史 Commit 時,自動切換到的某個中間版本剛好處於「程式碼正在重構、相依套件尚未安裝、或根本無法透過編譯工具執行」的半成品狀態。
  • 實務後果:測試腳本直接因為編譯失敗噴錯崩潰,導致系統無法判斷該 Commit 是正常還是異常。
  • 解法:git bisect 內建了 git bisect skip 指令。當遇到無法編譯或無關的 Commit 時,直接輸入該指令告訴系統跳過這個版本,Git 會改挑附近的另一個 Commit 讓你測試。使用 git bisect run 時,測試腳本回傳 125 也會自動跳過目前的 Commit。

3. 依賴自動化執行卻未正確處理測試環境的動態干擾

  • 踩坑情境:工程師為了求快,直接執行自動化整合測試,但專案中的測試項目含有會受網路延遲或時間差影響的不穩定測試。
  • 實務後果:同一個 Commit 跑兩次,一次通過、一次失敗,導致自動二分搜尋誤判兇手 Commit,整條二分搜尋路徑全部錯亂。

💡 示意案例:全域設定檔汙染導致的幽靈 Bug

假設在維護一個大型單頁應用程式(SPA)時,專案在進入特定頁面時會無預警發生畫面崩潰。團隊起初毫無頭緒,決定採用二分搜尋除錯法:

  1. 先將路由進入點的 10 個初始化子模組直接註解掉後半部(留下前 5 個)。
  2. 測試發現正常,於是將範圍縮小至後 5 個模組。
  3. 透過二分夾擠與提早 return,最後鎖定是第 8 個模組中的某行全域狀態讀取引發錯誤。

然而,深入一看才發現——第 8 個模組本身寫得完全沒問題,真正的禍首是因為第 7 個模組在某次 Commit 中悄悄修改了共用全域變數的型別,導致第 8 個模組在讀取時抓到未定義的空值而崩潰。這個案例告訴我們:二分搜尋幫我們縮小了崩潰發生點,但排查時仍需配合版本歷史或狀態追蹤,才能找出真正的引發根源。

參考資料與延伸閱讀

發佈留言