Binary search — 二分搜尋法

photo by @kellysikkema

利用將資料切一半的方式來做搜尋，舉例來說，如果要從數字1–100猜終極密碼，如果採用線性搜尋法就是一個一個問?是1嗎?是2嗎?…依序猜下去，很不幸的數字剛好是99就需要猜99次，但如果用二分搜尋法就會是先判斷數字是否大於50 ，如果是的話那是否大於75 ，依此類推每次都用對半砍的方式縮小範圍，最後只需要猜七次就能猜出終極密碼。

每次都將搜尋範圍縮減1/2

使用二分搜尋法的前提必須是先排序過

假設目前有個陣列:[10, 21, 34, 50, 66,79, 82, 97]，要找出陣列中是否有79這個數字，有的話就回傳79在哪個index

這邊運用到雙指針的概念來解題(left, right)，關於雙指針的說明可以參考這篇文章， 這裡可以先想像有兩個指針會不斷往中間靠攏，進而縮短搜尋區間。

實作的概念為:

1. 先在陣列取一個中間數的index，公式為 Math.floor((left+right)/2)，0+7除以2無條件捨去後拿到3，這邊用middle標示為中間數。

上方黃色小字為index

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)