跳至主要内容

Binary Search

Binary Search（二分搜尋）是一種在已排序的陣列中尋找目標值的演算法。它的基本概念是透過將目標值與陣列的中間值比較，來決定目標值位於左邊還是右邊，從而將搜尋範圍縮小一半。這樣持續縮小搜尋範圍，直到找到目標值或搜尋範圍變成空的。

Binary Search 的時間複雜度是 O(log n)，其中 n 代表陣列的大小。這讓 Binary Search 成為一種相當有效率的搜尋方法，特別是在處理大型陣列時。

Binary Search 的實作​

以下是 Binary Search 的簡單實作，在這段程式碼中，我們使用 left 和 right 兩個指標來表示搜尋範圍的左右邊界。接著，在迴圈中計算中間值 mid，並將其與目標值進行比較。如果 arr[mid] 等於目標值，則返回 mid；如果不等，則根據比較結果調整 left 或 right 的值，繼續搜尋。

/**
 * @param {Array<number>} arr The input integer array to be searched.
 * @param {number} target The target integer to search within the array.
 * @return {number} The index of target element in the array, or -1 if not found.
 */
export default function binarySearch(arr, target) {
  // Initialize the left and right indices of the array
  let left = 0;
  let right = arr.length - 1;

  // Keep searching until the left and right indices meet.
  while (left <= right) {
    // Calculate the mid index to retrieve the mid element later.
    const mid = Math.floor((left + right) / 2);

    if (target < arr[mid]) {
      // If the target element is less than the middle element,
      // search the left half of the array.
      // Adjust the right index so the next loop iteration
      // searches the left side.
      right = mid - 1;
    } else if (target > arr[mid]) {
      // If the target element is greater than the middle element,
      // search the right half of the array.
      // Adjust the left index so the next loop iteration
      // searches the left side.
      left = mid + 1;
    } else {
      // If the target element is equal to the middle element,
      // return the index of the middle element.
      return mid;
    }
  }

  // If the element is not found, return -1.
  return -1;
}

const arr = [1, 3, 5, 7, 9, 11, 13];

console.log(binarySearch(arr, 7)); // Output: 3