掌握 JavaScript 和 Java 中的二分搜尋：逐步指南-java教程-PHP中文網

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

什麼是二分查找？

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

以下是進階概述：

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

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

JavaScript 和 Java 中的迭代二分搜尋

Mastering Binary Search in JavaScript and Java: A Step-by-Step Guide — 對於喜歡循環的人。

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.");
        }
    }
}

登入後複製