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

登录后复制