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)。