掌握 JavaScript 和 Java 中的二分搜尋：逐步指南

二分搜尋是每個開發人員都應該理解的基本演算法，它提供了一種高效的方法來搜尋排序數組中的元素。該演算法依賴於「分而治之」的方法，允許每一步將搜尋空間減半。在本文中，我們將探索 JavaScript 和 Java 中的二分搜索，涵蓋迭代和遞歸實作。

什麼是二分查找？

二分搜尋是一種旨在尋找排序數組中目標值的位置的演算法。透過利用陣列的排序特性，二分搜尋有效地縮小了搜尋空間，實現了 O(log n) 的時間複雜度。這比大型資料集中的線性搜尋快得多。

以下是進階概述：

1. 以兩個指標開始，startIndex 和 endIndex，代表目前搜尋範圍。
2. 計算startIndex和endIndex之間的中間索引（midIndex）。
3. 將中間元素與目標進行比較：
   • 如果與目標匹配，則返回索引。
   • 如果中間元素大於目標，則目標一定在左半部分，所以調整endIndex。
   • 如果中間元素小於目標，則目標一定在右半部分，所以調整startIndex。
4. 重複這個過程，直到找到目標或startIndex超過endIndex，表示目標不在陣列中。

讓我們深入研究程式碼範例。

---

JavaScript 和 Java 中的迭代二分搜尋

JavaScript 實作

在 JavaScript 中，迭代方法使用迴圈來執行二分搜尋。它看起來像這樣：

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Java實作

在Java中，迭代實作非常相似，只是Java語法有所調整：

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

解釋

在兩種實作中：

• 我們分別將 startIndex 和 endIndex 設定為陣列的開頭和結尾。
• 每次迭代都會找到中間索引 midIndex，並將 arr[midIndex] 與目標進行比較。
  • 如果 arr[midIndex] 等於 target，我們回傳 midIndex。
  • 如果 arr[midIndex] 小於 target，我們將 startIndex 移到 midIndex 1，將搜尋範圍縮小到右半部。
  • 如果 arr[midIndex] 大於 target，我們將 endIndex 移到 midIndex - 1，將搜尋範圍縮小到左半部。
• 如果 startIndex 超過 endIndex，則循環退出，這表示目標不在陣列中。

---

JavaScript 和 Java 中的遞歸二分搜尋

對於遞歸方法，我們定義函數，以便它使用更新的索引來呼叫自身，直到找到目標或搜尋範圍為空。

JavaScript 實作

在 JavaScript 中，這是一個遞歸二分搜尋實作：

const binarySearch = (arr, target) => {
  let startIndex = 0;
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    let midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] === target) {
      return midIndex; // Target found
    } else if (arr[midIndex] < target) {
      startIndex = midIndex + 1; // Search in the right half
    } else {
      endIndex = midIndex - 1; // Search in the left half
    }
  }
  return -1; // Target not found
};

let nums = [-1, 0, 3, 5, 9, 12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Java實作

在Java中，類似的遞歸二分查找可以實現如下：

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int startIndex = 0;
        int endIndex = arr.length - 1;

        while (startIndex <= endIndex) {
            int midIndex = (startIndex + endIndex) / 2;

            if (arr[midIndex] == target) {
                return midIndex; // Target found
            } else if (arr[midIndex] < target) {
                startIndex = midIndex + 1; // Search in the right half
            } else {
                endIndex = midIndex - 1; // Search in the left half
            }
        }
        return -1; // Target not found
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;

        int result = binarySearch(nums, target);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

遞歸版本如何運作

在每次遞迴呼叫中：

• 計算中間索引 midIndex。
• 如果 arr[midIndex] 與目標匹配，則傳回索引。
• 如果 arr[midIndex] 大於目標，則在左半部繼續搜尋（endIndex 變成 midIndex - 1）。
• 如果 arr[midIndex] 小於目標，則在右半部繼續搜尋（startIndex 變成 midIndex 1）。
• 基本情況 if (startIndex > endIndex) 確保在未找到目標時遞歸停止。

---

複雜性分析

• 時間複雜度：迭代和遞歸版本的時間複雜度均為 O(log n)，因為每一步都會將搜尋空間減半。
• 空間複雜度：迭代方法的空間複雜度為 O(1)，而遞歸方法由於呼叫堆疊的原因，空間複雜度為 O(log n)。

何時使用二分查找

二分搜尋在以下情況下是理想的選擇：

• 陣列已排序：二分查找僅適用於排序數組。
• 效率至關重要：其 O(log n) 時間複雜度對於大型資料集來說非常有效率。

如果數組未排序，請考慮先對其進行排序（以 O(n log n) 成本），或者如果資料集較小，則使用線性搜尋。

---

結論

二分搜尋是一種通用且高效的演算法，用於在排序數組中定位元素。無論您選擇迭代還是遞歸方法，了解二分搜尋對於提高應用程式的效能都很有價值。嘗試 JavaScript 和 Java 中的兩種實現，了解它們的工作原理，並查看哪種最適合您的特定用例。

---

？參考

• 二分查找
• Grouking 演算法
• 大 O 表示法

？跟我說話

• 領英
• Github
• 投資組合

以上是掌握 JavaScript 和 Java 中的二分搜尋：逐步指南的詳細內容。更多資訊請關注PHP中文網其他相關文章！