problem

輸入為一個元素為整數的有序陣列和一個整數 target，以二元搜尋檢查 target 是否在陣列中，有則回傳索引值，否則回傳 -1。

sample input:
array = [0, 1, 21, 32, 45, 45, 61, 71, 72, 73],
target = 32

sample output:
3

二元搜尋是利用有序序列的特性，每一次排除一半的選項來將問題縮小，以此快速找到特定值。
程式碼實作的步驟是：

1. 以 left, right 兩個指標分別指向陣列第一個和最後一個數字。
2. 以兩個指標計算出中央數字的索引 mid。
3. 比較中央數字和目標數字。如果相等，代表找到目標，回傳 mid。若中央數字較小，代表比它更小的元素 (陣列左半邊) 都不需要考慮，所以更新 left = mid + 1；如果中央數字較大，代表比它大的元素 (陣列右半邊) 都不用考慮，所以更新 right = mid - 1。
4. 左右兩個指標不交錯的情況下，重複步驟 2-3，都沒有找到目標則最後回傳 -1。

n 為輸入陣列長度，
time: O(log(n))
space: O(1)

function binarySearch(array, target) {
  let left = 0, right = array.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

二元搜尋透過逐步削減問題來解決問題，或者說每一步驟就是對更小規模的輸入進行二元搜尋，所以也可以用遞迴表達。不過遞迴解法需考慮進堆疊，空間複雜度應為 O(log(n))。

function binarySearch(array, target) {
  return binarySearchHelper(array, target, 0, array.length - 1);
}

function binarySearchHelper(array, target, left, right) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (array[mid] === target) {
    return mid;
  } else if (array[mid] < target) {
    return binarySearchHelper(array, target, mid + 1, right);
  } else {
    return binarySearchHelper(array, target, left, mid - 1);
  }
}

最後，這篇文章結尾處有寫到以 left + (right – left) / 2; 和 (left + right) / 2; 這兩種方式來計算中間索引 (middle index) 會有什麼差別，提供參考。