Java 二分查找

JavaJavaBeginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

二分查找(Binary Search)是一种高效的搜索算法,用于在已排序的数组中查找特定值。它比线性查找更快,因为每次迭代后都会排除数组的一半。在本实验中,我们将学习如何在 Java 中实现二分查找算法的步骤。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL java(("`Java`")) -.-> java/BasicSyntaxGroup(["`Basic Syntax`"]) java(("`Java`")) -.-> java/DataStructuresGroup(["`Data Structures`"]) java(("`Java`")) -.-> java/ProgrammingTechniquesGroup(["`Programming Techniques`"]) java(("`Java`")) -.-> java/ObjectOrientedandAdvancedConceptsGroup(["`Object-Oriented and Advanced Concepts`"]) java/BasicSyntaxGroup -.-> java/while_loop("`While Loop`") java/DataStructuresGroup -.-> java/arrays("`Arrays`") java/DataStructuresGroup -.-> java/arrays_methods("`Arrays Methods`") java/DataStructuresGroup -.-> java/sorting("`Sorting`") java/DataStructuresGroup -.-> java/collections_methods("`Collections Methods`") java/ProgrammingTechniquesGroup -.-> java/recursion("`Recursion`") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/arraylist("`ArrayList`") subgraph Lab Skills java/while_loop -.-> lab-117471{{"`Java 二分查找`"}} java/arrays -.-> lab-117471{{"`Java 二分查找`"}} java/arrays_methods -.-> lab-117471{{"`Java 二分查找`"}} java/sorting -.-> lab-117471{{"`Java 二分查找`"}} java/collections_methods -.-> lab-117471{{"`Java 二分查找`"}} java/recursion -.-> lab-117471{{"`Java 二分查找`"}} java/arraylist -.-> lab-117471{{"`Java 二分查找`"}} end

创建排序数组

二分查找算法需要一个已排序的数组,因此我们首先创建一个排序数组。

int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

迭代实现二分查找

我们现在将迭代实现二分查找算法。如果目标元素存在于数组中,该方法会返回其索引;否则,返回 -1。

public static int binarySearchIterative(int[] sortedArray, int key) {
    int leftIdx = 0;
    int rightIdx = sortedArray.length - 1;
    while (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            rightIdx = midIdx - 1;
        } else
            leftIdx = midIdx + 1;
    }
    return -1;
}

要运行代码,我们首先需要调用 binarySearchIterative 方法,并将 sortedArray 和要查找的元素作为参数传入。

## 编译 Java 文件
javac BinarySearch.java

## 运行文件
java BinarySearch

递归实现二分查找

我们现在将递归实现二分查找算法。如果目标元素存在于数组中,该方法同样会返回其索引;否则,返回 -1。

public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx) {
    if (leftIdx <= rightIdx) {
        int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
        if (sortedArray[midIdx] == key)
            return midIdx;
        else if (sortedArray[midIdx] > key) {
            return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1);
        } else
            return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);
    } else
        return -1;
}

要运行代码,我们需要调用 binarySearchRecursive 方法,并将 sortedArray、要查找的元素、leftIdxrightIdx 作为参数传入。

使用内置方法实现二分查找

Java 中也提供了内置函数来实现二分查找。这些函数是 Arrays.binarySearch()Collections.binarySearch()。我们可以使用这些函数在已排序的数组中查找元素。

Arrays.binarySearch() 函数接受一个已排序的数组和要查找的键值作为参数。如果键值存在于数组中,函数会返回其索引;否则,返回 -1。

int index = Arrays.binarySearch(sortedArray, 6);

Collections.binarySearch() 函数可以用于像 ArrayList 这样的集合中查找元素。该函数接受已排序的集合和键值作为参数,并返回键值所在的索引。如果键值不存在,则返回 -1。

ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
int index = Collections.binarySearch(sortedList, 6);

测试

我们现在将测试所有方法并打印输出结果。

public static void main(String[] args) {
    int[] sortedArray = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int key = 12;
    System.out.println("Element " + key + " is present at index: " + binarySearchIterative(sortedArray, key));
    System.out.println("Element " + key + " is present at index: " + binarySearchRecursive(sortedArray, key, 0, sortedArray.length - 1));
    System.out.println("Element " + key + " is present at index: " + Arrays.binarySearch(sortedArray, key));
    ArrayList<Integer> sortedList = new ArrayList<Integer>(Arrays.asList(2, 4, 6, 8, 10, 12, 14, 16, 18, 20));
    System.out.println("Element " + key + " is present at index: " + Collections.binarySearch(sortedList, key));
}

要运行代码,我们首先需要编译 Java 程序。

javac BinarySearch.java

然后可以运行程序。

java BinarySearch

总结

本实验涵盖了在 Java 编程语言中迭代和递归实现二分查找算法的步骤。我们还学习了如何使用内置方法 Arrays.binarySearch()Collections.binarySearch() 来实现二分查找。我们创建了一个已排序的数组,并使用不同的方法在其中查找元素。

您可能感兴趣的其他 Java 教程