掌握 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中文网其他相关文章！