使用 JavaScript 進行二分查詢演算法在陣列中搜索

---

在 JavaScript 程式設計領域，能夠使用二分查詢演算法有效地搜尋陣列具有極其重要的意義。這種演算法技術通常被認為是一種優雅而強大的解決方案，它為開發人員提供了一種高效能的方法來在已排序的陣列中定位所需元素。掌握使用 JavaScript 進行二分查詢不僅展示了個人在演算法問題解決方面的熟練程度，還使開發人員能夠最佳化其應用程式中的搜尋操作。在本文中，我們將深入探討在 JavaScript 中實現二分查詢的細節，探索其分步過程，並揭示這種強大演算法技術領域中很少使用的詞彙。

問題陳述

手頭的問題涉及在已排序的陣列中搜索目標元素，而傳統的線性搜尋方法由於其時間複雜度，對於較大的陣列而言效率低下。

示例輸入 -

Array: [2, 5, 8, 12, 16, 23, 38, 42, 57, 69]
Target Element: 23

示例輸出 -

The target element 23 was found at index 5.

方法

在本文中，我們將看到多種在 JavaScript 中解決上述問題陳述的方法 -

• 迭代二分查詢

• 遞迴二分查詢

• 陣列方法

方法 1：迭代二分查詢

在迭代二分查詢中，將 low 和 high 初始化為最低和最高索引。進入一個 while 迴圈，直到 low 小於或等於 high。計算 mid 為 low 和 high 的平均值。檢查 mid 處的數值是否與目標匹配。如果匹配，則返回 mid，表示匹配成功。如果 mid 處的數值小於目標，則將 low 更新為 mid + 1 以在右半部分搜尋。如果 mid 處的數值大於目標，則將 high 更新為 mid - 1 以在左半部分搜尋。如果 while 迴圈完成而未找到目標，則返回 -1 以指示未找到。

示例

binarySearch 函式接受一個數組和一個目標值。它將 low 和 high 初始化為搜尋空間的最低和最高索引。使用 while 迴圈，它計算 mid 索引並檢查數值是否與目標匹配。如果匹配，則返回 mid 索引。如果數值小於目標，則更新 low；如果大於，則更新 high。如果迴圈結束而未找到目標，則返回 -1。

function binarySearch(array, target) {
   let low = 0;
   let high = array.length - 1;

   while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      if (array[mid] === target) {
         return mid; // Target found at index mid
      } else if (array[mid] < target) {
         low = mid + 1; // Discard the left half
      } else {
         high = mid - 1; // Discard the right half
      }
   }
   return -1; // Target not found
}
const array = [2, 5, 8, 12, 16, 23, 38, 42, 57, 69];
const target = 23;
console.log(`Target found at index: ${binarySearch(array, target)}`);

輸出

以下是控制檯輸出 -

Target found at index: 5

方法 2：遞迴二分查詢

在遞迴二分查詢中，定義了一個名為 binarySearch 的函式，其引數為陣列、目標值、low 和 high 索引。它檢查 low 是否大於 high，如果為真則返回 -1。mid 索引計算為 low 和 high 的平均值。如果 mid 索引處的數值與目標匹配，則返回 mid 索引。如果 mid 索引處的數值小於目標，則遞迴呼叫 binarySearch 函式，搜尋空間為右半部分。如果 mid 索引處的數值大於目標，則遞迴呼叫 binarySearch 函式，搜尋空間為左半部分。此過程持續進行，直到找到目標或搜尋空間用盡，如果未找到目標則返回 -1。

示例

binarySearch 函式是一個遞迴實現，它在陣列中搜索目標值。它透過比較 low 和 high 索引來檢查搜尋空間是否為空。如果是，則返回 -1。否則，它計算 mid 索引，檢查 mid 處的數值是否與目標匹配，如果匹配則返回 mid。如果 mid 處的數值小於目標，則遞迴呼叫自身，搜尋空間為右半部分。如果 mid 處的數值大於，則遞迴呼叫自身，搜尋空間為左半部分。此過程持續進行，直到找到目標或確定目標不存在。

function binarySearch(array, target, low = 0, high = array.length - 1) {
   if (low > high) {
      return -1; // Target not found
   }
   let mid = Math.floor((low + high) / 2);
   if (array[mid] === target) {
      return mid; // Target found at index mid
   } else if (array[mid] < target) {
      return binarySearch(array, target, mid + 1, high); // Search the right half
   } else {
      return binarySearch(array, target, low, mid - 1); // Search the left half
   }
}
const array = [2, 5, 8, 12, 16, 23, 38, 42, 57, 69];
const target = 23;
console.log(`Target found at index: ${binarySearch(array, target)}`);

輸出

以下是控制檯輸出 -

Target found at index: 5

方法 3：陣列方法

binarySearch 函式接受一個數組和一個目標值作為引數。它使用 indexOf() 方法來查詢目標值，並將結果賦給 index 變數。透過檢查 indexOf() 方法是否產生一個與 -1 不同的值，它確定是否存在匹配。如果檢測到匹配，則函式輸出索引。但是，如果 indexOf() 方法返回 -1，表示目標不存在，則函式返回 -1 以傳達此狀態。

示例

binarySearch 函式接受一個數組和一個目標值作為引數，並使用 indexOf() 方法來確定目標在陣列中的索引。它將結果賦給 index 變數，如果找到目標則返回索引。或者，如果未找到目標，則返回 -1。

function binarySearch(array, target) {
   const index = array.indexOf(target);
   return index !== -1 ? index : -1;
}
const array = [2, 5, 8, 12, 16, 23, 38, 42, 57, 69];
const target = 23;
console.log(`Target found at index: ${binarySearch(array, target)}`);

輸出

以下是控制檯輸出 -

Target found at index: 5

結論

總之，使用 JavaScript 在陣列中搜索時使用二分查詢演算法可能是一種非常有效的方法。透過利用演算法的對數時間複雜度，我們可以加快搜索過程並最佳化效能，尤其是在處理較大的陣列時。明智地實施二分查詢使開發人員能夠有效地定位所需元素，從而改善使用者體驗並增強應用程式功能。因此，將此方法整合到 JavaScript 程式碼中對於處理大量資料集和實現簡化的搜尋操作可能非常寶貴。