Java 中的线性搜索一直是在数组中查找元素的首选方法。它按顺序搜索数组的每个元素并且非常容易实现。但是，当所讨论的数组包含数万个元素时，线性搜索的缺点就很明显了。在这种情况下，二进制搜索实现的“分而治之”方法效率更高，对于考虑时间和空间复杂性的程序员来说更可取。
![Java 中的二进制搜索：递归、迭代和 Java 集合 - 1]()
二进制搜索
在二进制搜索中，一个数组被重复分成两半，直到找到键（正在搜索的元素）。该划分是虚拟的，即保持数据的完整性。每次迭代，都会关注数组的中间值。如果该值等于我们要查找的键，则循环或递归函数终止。否则，它将继续循环。如果中间值大于键，则函数将关注数组的前半部分，反之亦然。重复此过程，直到找到键或遍历整个数组。
线性搜索和二分搜索之间的区别
| 线性搜索 | 二进制搜索 |
|---|---|
| 顺序搜索数组 | 将数组分成两半，直到找到值 |
| 适用于任何阵列 | 仅适用于排序数组 |
| 复杂度为 O(N) | 复杂度为 O(log2N) |
| 可以处理排序和未排序的数组 | 只能在排序数组上实现。 |
| 实施起来不那么复杂 | 实施起来更复杂 |
二进制搜索算法
下面给出二分查找的算法。- 确定数组的第一个和最后一个点。这些点将在每次迭代时根据数组和正在搜索的键进行调整。
- 遍历数组并比较当前第一个点和最后一个点之间的中间值。在第一次迭代中，第一个和最后一个变量将与数组中的实际变量相同。
- 如果键大于中间值，则该值的索引将存储在新的“First”变量中。
- 如果键小于中间值，则该值的索引将存储在“最后”变量中。
- 重复此条件，直到两个条件之一变为真：
- 钥匙找到了。
- 整个数组已经迭代。
迭代二进制搜索
下面给出了使用迭代方法进行二分查找的代码。
import java.util.Scanner;
public class IterativeBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchIterative(arr,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchIterative(int[] arr, int num){
//Representing the Start and End Index After Division of Array
int start = 0;
int end = arr.length;
//Loop to Iterate Through the Array
for(int i = 0; iarr[n]){
start = n;
}
//If number to search for is greater than the arr value at index 'n'
else{
end = n;
}
}
//If number isn't found, return -1
return -1;
}
}
递归二分查找
下面给出了使用递归的二进制代码。
import java.util.Scanner;
public class RecursiveBinarySearch {
public static void main(String[] args) {
int arr[] = {1,3,6,8,10};
System.out.println("Enter Number to Search For: ");
Scanner input = new Scanner (System.in);
int num = input.nextInt();
int result = BinarySearchRecursive(arr,0,arr.length-1,num);
if(result!=-1)
System.out.println("Value Found at Index #" + result);
else
System.out.println("Value Not Found");
}
public static int BinarySearchRecursive(int arr[], int a, int b, int num){
//Base Case to Exit the Recursive Function
if (b < 1) {
return -1;
}
int n = a + (b=1)/2;
//If number is found at mean index of start and end
if(arr[n]==num)
return n;
//If number to search for is greater than the arr value at index 'n'
else if(arr[n]>num)
return BinarySearchRecursive(arr,a,n-1,num);
//If number to search for is greater than the arr value at index 'n'
else
return BinarySearchRecursive(arr,n+1,b,num);
}
}
GO TO FULL VERSION