Java 中的二进制搜索：递归、迭代和 Java 集合

Java 中的线性搜索一直是在数组中查找元素的首选方法。它按顺序搜索数组的每个元素并且非常容易实现。但是，当所讨论的数组包含数万个元素时，线性搜索的缺点就很明显了。在这种情况下，二进制搜索实现的“分而治之”方法效率更高，对于考虑时间和空间复杂性的程序员来说更可取。

二进制搜索

在二进制搜索中，一个数组被重复分成两半，直到找到键（正在搜索的元素）。该划分是虚拟的，即保持数据的完整性。每次迭代，都会关注数组的中间值。如果该值等于我们要查找的键，则循环或递归函数终止。否则，它将继续循环。如果中间值大于键，则函数将关注数组的前半部分，反之亦然。重复此过程，直到找到键或遍历整个数组。

线性搜索和二分搜索之间的区别

二进制搜索算法

下面给出二分查找的算法。

1. 确定数组的第一个和最后一个点。这些点将在每次迭代时根据数组和正在搜索的键进行调整。
2. 遍历数组并比较当前第一个点和最后一个点之间的中间值。在第一次迭代中，第一个和最后一个变量将与数组中的实际变量相同。
3. 如果键大于中间值，则该值的索引将存储在新的“First”变量中。
4. 如果键小于中间值，则该值的索引将存储在“最后”变量中。
5. 重复此条件，直到两个条件之一变为真：
   • 钥匙找到了。
   • 整个数组已经迭代。

下面给出了迭代二分搜索和递归二分搜索的代码。

迭代二进制搜索

下面给出了使用迭代方法进行二分查找的代码。

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);
    }
 
}

时间复杂度

随着每一次迭代，数组即搜索空间被分成两半。在每次迭代“m”之后，搜索空间的大小将变为 N/2m。在最坏的情况下，我们只会在数组的另一侧留下一个元素。这时二分查找的复杂度就会是k = log2N。线性搜索的时间复杂度为 O(N)，这导致二分搜索的速度更快，复杂度为 O(log2N)。这是使用二分搜索优于线性搜索的主要好处。

空间复杂度

二分搜索使用三个不同的变量——开始、结束和中间。这三个变量被创建为指向数组索引的内存位置的指针。因此，二进制搜索在空间上非常有效。迭代二分查找的空间复杂度为 O(1)。对于递归实现，它是 O(log N)。