二分搜尋法是一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始,如果中間元素正好是要搜尋的元素,則搜尋過程結束;如果某一特定元素大於或者小於中間元素,則在陣列大於或小於中間元素的那一半中搜尋,而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空,則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
二分搜尋法的過程
假設現在有個已排序好的整數陣列,內容如下:

用二元搜尋法來找到元素69。這邊可以看到此陣列的長度為10,是偶數,所以並不能剛好選到正中間的元素,不過這也沒關係,選擇索引4或是索引5都可以,在此以索引4為例。

由於我們要找的元素69比索引4的元素值38還要來得大,因此可以知道若元素值69存在於該陣列的話,那麼它一定是在索引值大於4的位置,索引值小於4的元素們就都不用去管了。所以下一次搜尋,我們要選擇索引5到索引9的中間元素,也就是索引7。

二分搜尋法實作
function binary_earch(data, target) {
//宣告變日數都是 索引值 index
let start = 0
let end = data.length - 1
let middle
while (start <= end) {
//取中間值
middle = Math.floor((start + end) / 2)
//判斷搜尋左右方向
if (target < data[middle]) {
//向右邊尋找
end = middle - 1
} else if (target > data[middle]) {
//向左邊尋找
start = middle + 1
} else {
return middle //回傳資料結構中的 索引值 index
}
}
return -1 //未找到回傳 -1
}
let arr = [2,30,32,38,47,61,69,79,81]
console.log(binary_earch(arr, 38)) //3 回傳資料結構中的 索引值 index