這次要介紹的是二分搜尋法(Binary Search)，使用此排序法的話，要搜尋的資料列必須經過排序。運作原理就是將要尋找的值和資料列中間的值進行比較。
如果尋找的值比中間值小，就往左邊的子陣列再找中間值再做比較，直到找到值為止。
如果尋找的值比中間值大，就往右邊的子陣列再找中間值再做比較，直到找到值為止。

接著我們來實作吧!完成後會討論其時間複雜度~

1. 先設定左邊界點和右邊界點的索引位置，並在左邊界點小於右邊界點的情況下設定中間值的位置。

2. 開始將尋找值和資料列的值進行比較，若尋找值和中間值剛好相同，直接回傳中間值的索引位置，假如尋找值比中間值大時，讓中間值後的一個元素位置指定 left，在符合條件的狀況下重新執行 while 迴圈，再次取到新的中間值，然後不斷比較下去，直到找到和尋找值相同的值為止。

3. 若都沒有找到和尋找值相同的值，就回傳 -1，程式結束。

function binarySearch(data, key) {
  let left = 0;
  let right = data.length -1;
  let middle;
  while(left <= right) {
    middle = Math.floor((left + right) / 2);
    if(data[middle] == key) {
      return middle;
    } else if(key > data[middle]) { // 尋找值比中間值大時，讓中間值後的一個元素位置指定left
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  return -1;
}

時間複雜度:

• 最佳時間複雜度：O(1)
  一開始資料列的中間元素就是我們想找的元素
• 平均時間複雜度：O(log n)
• 最差時間複雜度：O(log n)

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day23-binary-search.js

搜尋相關的兩個演算法都介紹完畢，從明天起將會介紹一些題目來做實作。