Binary search — 二分搜尋法
Published in
Dec 20, 2021
利用將資料切一半的方式來做搜尋,舉例來說,如果要從數字1–100猜終極密碼,如果採用線性搜尋法就是一個一個問?是1嗎?是2嗎?…依序猜下去,很不幸的數字剛好是99就需要猜99次,但如果用二分搜尋法就會是先判斷數字是否大於50 ,如果是的話那是否大於75 ,依此類推每次都用對半砍的方式縮小範圍,最後只需要猜七次就能猜出終極密碼。
使用二分搜尋法的前提必須是先排序過
假設目前有個陣列:[10, 21, 34, 50, 66,79, 82, 97],要找出陣列中是否有79這個數字,有的話就回傳79在哪個index
這邊運用到雙指針的概念來解題(left, right),關於雙指針的說明可以參考這篇文章, 這裡可以先想像有兩個指針會不斷往中間靠攏,進而縮短搜尋區間。
實作的概念為:
- 先在陣列取一個中間數的index,公式為 Math.floor((left+right)/2),0+7除以2無條件捨去後拿到3,這邊用middle標示為中間數。
2. 這時拿目標數79去跟中間數50比較,目標數79比較大,代表中間數的左邊那堆數字都不可能是我們要找的答案(都太小了),所以我們要調整一下搜尋範圍,將left指針移動到middle+1的位置。
為甚麼要middle+1?因為已經知道middle不是答案,搜尋範圍就可以排除middle了
3.重新計算中間數,(4+7)/2無條件捨去算出5,而在index 5的數字79就是我們要找的數字。
用js實作二分搜尋法
時間複雜度
👍在最差的情況下, 時間複雜度是O(log n)
👎在最佳的情況下 , 時間複雜度是O(1)
🤚在平均情況下,時間複雜度為 O(log n)