基本演算法介紹--搜尋

基本演算法介紹-搜尋

二分搜尋法（Binary Search）

玩1到100的終極密碼，一個個從頭慢慢猜最壞要猜100次。但用二分搜尋法（Binary Search）每次從中剖半，留下正確的部分再剖半，7次就能猜出來了。當放大到40億個數字的終極密碼，一個個從頭慢慢猜最壞要猜40億次；後者只要32次就能猜出來了。

如果搜尋的數列已經有排序，應該儘量利用它們已排序的特性，以減少搜尋比對的次數，這是搜尋的基本原則，二分搜尋法是這個基本原則的代表。

資料來源:Animations from Grokking Algorithms

原始影片https://goo.gl/NM3eku

A.圖解

首先，我們將搜尋問題簡化為數字的搜尋。假設原始資料有：5、8、10、1、7 這 5 個隨機數字，在二分搜尋法中，我們先打開最中間的櫃子，發現裡面的數字是 41。因為 55 比 41 大，因此我們知道從一號櫃到三號櫃都不會有 55，接下來只需要檢查五號櫃到七號櫃。同樣的邏輯，我們打開剩下三個可能性中最中間的櫃子，發現六號櫃裡面的數字是 61，因為 61 比 55 大，我們可以知道七號櫃的數字一定也比 55 大，得知 55 一定就在五號櫃之中。