简介
二分查找(Binary Search)是一种高效的搜索算法,用于在已排序的数组中查找特定值。它比线性查找更快,因为每次迭代后都会排除数组的一半。在本实验中,我们将学习如何在 Java 中实现二分查找算法的步骤。
二分查找(Binary Search)是一种高效的搜索算法,用于在已排序的数组中查找特定值。它比线性查找更快,因为每次迭代后都会排除数组的一半。在本实验中,我们将学习如何在 Java 中实现二分查找算法的步骤。
二分查找算法需要一个已排序的数组,因此我们首先创建一个排序数组。
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
、要查找的元素、leftIdx
和 rightIdx
作为参数传入。
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()
来实现二分查找。我们创建了一个已排序的数组,并使用不同的方法在其中查找元素。