二分搜尋法

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

二分搜尋法的過程

假設現在有個已排序好的整數陣列，內容如下：

用二元搜尋法來找到元素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