二分搜尋演算法(Binary Search)

假設有天你要在電話簿找一個K開頭的人，或是O開頭的人 你並不會從A開始找 一定是從最接近的開始找。

二分搜尋是一種演算法

下方是二分搜尋演算法的如何作用

STEP 1

圖一這是一組陣列，由小到大排列，其中我們在這陣列要找的數字是“13”所以我們必須把它存在 searchForNumber 這個變數裡面 (變數是關聯一個資料型態、儲存的值與儲存空間的位址值)

let searchForNumber = 13

圖一

STEP 2

尋找裡數字最大的跟數字最小的，當想取得中間值就可以使用(LOW+HIGH)/2

黃色是最小的數字 綠色是中間數字 紅色是最大的數字

現在可以開始使用二分搜尋

STEP 3 二分搜尋例子

let findBinary = function (list, targe) {
　　let low = 0;
　　let high = list.length - 1;  // 抓取二分搜尋最大跟最小的長度
　　while (low <= high) { // 為了可以不斷地縮小範圍尋找
　　　　let mid = Math.floor((low + high) / 2);
　　　　let guess = list[mid]
　　　　if (guess === targe) {
　　　　　　return mid
　　　　}

　　　　if (guess > targe) {
　　　　　　high = mid - 1;
　　　　} else {
　　　　　　low = mid + 1;
　　　　}
　　}
　　return null
}
findBinary([2,3,6,8,9,13,20],13) // index = 5

　　 index
[2] = 0
[3] = 1
[6] = 2
[8] = 3
[9] = 4
[13] = 5
[20] = 6

STEP 4

結論就會是上方的第五個index