二分搜尋法（Binary-search）

經典的搜尋法。

概念

跟玩終極密碼的方法一樣，假設有 1 到 100 個按照順序排好的數字，在猜數字時，我們通常會這樣做：

• 一開始猜 50 => 如果數字比 50 大，接著猜 51 ~ 100
• 接著猜 75 => 如果數字比 75 大，接著猜 76 ~ 100
• 接著猜 87 => 如果數字比 87 大，接著猜 88 ~ 100
• 以此類推…

每次都把所有可能拆成兩半，就是二分搜尋法的核心理念。但要切記的一點是，這只適用於「已經排列好的數列」。

實作－遞迴法

// 要遞迴的 function 
function binarySearchRecursively(array, targetElement, start, end) {
  // 左邊界 > 右邊界
  if (start > end) {
    return -1
  }

  // 中間位置（無條件捨去，取偏左邊那點）
  const middle = (start + end) >> 1

  /*
    目標 = 中間那個數字：
    找到數字了，直接回傳位置
    
    目標 > 中間的數字：
    代表前面的數字不用看了，把 start 設為中間位置往右移一位（+1）
    
    目標 < 中間的數字：
    代表後面的數字不用看了，把 end 設為中間位置往左移一位（-1）
  */
  if (targetElement === array[middle]) {
    return middle
  } else if (targetElement > array[middle]) {
    // 更新 start 後，遞迴 binarySearchRecursively
    return binarySearchRecursively(array, targetElement, middle + 1, end)
  } else {
    // 更新 end 後，遞迴 binarySearchRecursively
    return binarySearchRecursively(array, targetElement, start, middle - 1)
  }
}
// 用來執行 binarySearchRecursively
function binarySearch(array, targetElement) {
  return binarySearchRecursively(array, targetElement, 0, array.length-1)
}

const numbers = [1, 3, 24, 33, 57, 88, 99, 101]
console.log(binarySearch(numbers, 25))  // -1
console.log(binarySearch(numbers, 24))  // 2

詳細流程：

第一輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 7
middle: 3 number: 33

第二輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 2
middle: 1 number: 3

第三輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 2 end: 2
middle: 2 number: 24

第四輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 3 end: 2 => 到此為止，左邊界超出右邊界
result: -1

補充一

這裡要注意一點，(start > end) 不可以是 >=，要不然會漏掉一個搜尋：

第一輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 7
middle: 3 number: 33

第二輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 2
middle: 1 number: 3

第三輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 2 end: 2 => 到此為止，左邊界超出右邊界
result: -1

(middle: 2 number: 24) => 還沒有被搜尋到就 return -1 了

補充二

binarySearchRecursively(array, targetElement, 0, array.length-1) 中的 array.length - 1 不可以改寫成 array.length。

假設要找的數字是 101，最後就會去找 array[length] 這個數字，但這已經超出 array 的範圍了，所以會得到 undefined。這顯然不是件很好的事情，如果換個程式語言有可能就會直接噴 error，或是回傳一個奇怪的答案：

第一輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 102
start: 0 end: 8
middle: 4 number: 57

第二輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 102
start: 5 end: 8
middle: 6 number: 99

第三輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 102
start: 7 end: 8
middle: 7 number: 101

第四輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 102
start: 8 end: 8
middle: 8 number: undefined => 這裡很危險！

第五輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 102
start: 8 end: 7
value: -1 => 雖然最後還是能得到正確結果

實作－迴圈迭代法

function binarySearch(array, targetElement) {
  // 初始值：0 ~ array 的長度 -1 
  let start = 0
  let end = array.length - 1

  // 終止條件 左邊界 <= 右邊界
  while (start <= end) {
    // 中間位置（無條件捨去，取偏左邊那點）
    const middle = start + end >> 1 
    console.log('array:', array)
    console.log('target:', targetElement)
    console.log('start:', start, 'end:', end)
    console.log('middle:', middle, 'number:', array[middle])
    /*
      目標 = 中間那個數字：
      找到數字了，直接回傳位置
      
      目標 > 中間的數字：
      代表前面的數字不用看了，把 start 設為中間位置往右移一位（+1）
      
      目標 < 中間的數字：
      代表後面的數字不用看了，把 end 設為中間位置往左移一位（-1）
    */
    if (targetElement === array[middle]) {
      return middle
    } else if (targetElement > array[middle]) {
      start = middle + 1
    } else {
      end = middle - 1
    }
  }
  // 找不到目標數字，回傳 -1
  return -1
}

詳細步驟（跟剛剛差不多）：

第一輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 7
middle: 3 number: 33

第二輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 2
middle: 1 number: 3

第三輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 2 end: 2
middle: 2 number: 24
value: -1

補充

這裡一樣要注意 While (start <= end) 不可以寫成是 <，不然會忽略掉一個搜尋：

（兩者差別在於，遞迴是「= 時不能跳掉」，這裡是「= 要再找一次」）

第一輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 7
middle: 3 number: 33

第二輪
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 0 end: 2
middle: 1 number: 3
return -1 => 下一圈不會執行，所以這圈結束就會 return -1

下一圈（如果有執行的話）：
array: [1, 3, 24, 33, 57, 88, 99, 101]
target: 25
start: 2 end: 2
middle: 2 number: 24
value: -1

哪個方法比較好？

根據別人的說法是這樣：

在實作程式的時候，應該要避免使用遞迴(Recursive)的結構，因為遞迴需要不斷地重新建構函數的堆疊空間，硬體資源的負擔會比較大，且若是遞迴層數過多還會導致堆疊溢出(Stack Overflow)。所以比較好的做法還是在一個函數內以迴圈迭代的方式來完成。