新手第一個「聰明」演算法 —— 在排好序的資料裡,每問一次就丟掉一半。
只要你的資料已經排序,而且要「找某個東西在不在、在哪裡」,二分搜尋就是首選。一個一個找(線性搜尋)是 O(n),二分搜尋是 O(log n)——差距在資料量大的時候非常驚人:一百萬筆資料,線性最多要找一百萬次,二分搜尋只要約 20 次。
1. 用兩個指標 low、high 夾住整個搜尋範圍(頭和尾)。
2. 看正中間 mid 的值,拿它跟 target 比。
3. 中間剛好等於目標 → 找到了,收工。
4. 中間比目標小 → 答案在右半邊(low = mid + 1);中間比目標大 → 答案在左半邊(high = mid - 1)。回到第 2 步,直到範圍縮到空的為止。
「我想一個 1~100 的數字」——聰明的人會先猜 50,聽到「太小」就猜 75,每次砍一半,最多 7 次就中。
找「豬」不會從第一頁翻,而是翻到中間看在前面還後面,一直對半縮小。
電話簿照姓氏排好,你直接翻中間,不會一頁一頁找。
「二分法除錯」:先砍掉一半程式看還會不會錯,快速夾出出問題的那段。
選一個目標,按「下一步」看 low / mid / high 三個指標怎麼把範圍一半一半夾掉。試試 30(不存在),看它怎麼判斷「找不到」。
因為每一步都把範圍砍一半,問題規模是「一直除以 2」。反過來問「除以 2 幾次會變成 1」,就是 log₂:
資料變一千倍,只多找約 10 次——這就是對數時間可怕的地方。
從最基本的版本,到處理重複值、內建工具,最後到「在答案上二分」的進階技巧。
❌ 沒排序就用 —— 二分搜尋的前提是資料已排序,沒排序結果一定錯。
❌ 邊界少了等號 —— while low <= high 那個等號要在,不然會漏掉最後剩一個元素的情況。
❌ 忘了 +1 / -1 —— 寫成 low = mid 而不是 low = mid + 1,範圍可能卡住不縮,變成無窮迴圈。
❌ 溢位(其他語言) —— (low + high) 在 C/Java 可能爆掉,習慣寫 low + (high - low) // 2 較安全。Python 整數沒上限,但養成好習慣。
low = mid + 1 改成 low = mid,會出什麼問題?把答案打到對話裡,我幫你對。