Java での二分探索: 再帰的、反復的、および Java コレクション

Java における線形検索は、配列内の要素を見つけるための頼りになる方法です。配列の各要素を順番に検索し、実装が非常に簡単です。ただし、問題の配列に数万の要素が含まれている場合、線形検索の欠点は明らかです。このような場合、二分探索によって実装される「分割統治」方法ははるかに効率的であり、時間と空間の複雑さを考慮するプログラマーにとって好ましいものです。

二分探索

二分探索では、キー (検索対象の要素) が見つかるまで、配列が繰り返し 2 つの半分に分割されます。分割は仮想的です。つまり、データの整合性は維持されます。反復のたびに、配列の中央の値が注目されます。値が探しているキーと等しい場合、ループまたは再帰関数は終了します。それ以外の場合はループし続けます。中央の値がキーより大きい場合、関数は配列の前半に焦点を当てます。逆も同様です。このプロセスは、キーが見つかるまで、または配列全体が反復されるまで繰り返されます。

線形探索と二分探索の違い

二分探索アルゴリズム

二分探索のアルゴリズムは以下の通りです。

1. 配列の最初と最後の点を決定します。ポイントは、検索される配列とキーに応じて反復ごとに調整されます。
2. 配列を反復処理し、現在の最初の点と最後の点の中間値を比較します。最初の反復では、最初と最後の変数は配列内の実際の変数と同じになります。
3. キーが中間値より大きい場合、その値のインデックスが新しい「First」変数に格納されます。
4. キーが中央の値より小さい場合、その値のインデックスは「Last」変数に格納されます。
5. この条件は、次の 2 つの条件のいずれかが true になるまで繰り返されます。
   • 鍵が見つかりました。
   • 配列全体が反復されました。

反復二分探索と再帰二分探索の両方のコードを以下に示します。

反復二分探索

反復法による二分探索のコードを以下に示します。

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 のサイズに変化します。最悪の場合のシナリオでは、配列の反対側の 1 つの要素だけが残ることになります。このとき、二分探索の計算量は k = log2N となります。線形探索の時間計算量は O(N) であり、その結果、二分探索は O(log2N) の計算量ではるかに高速になります。これは、線形検索よりも二分検索を使用する主な利点です。

空間の複雑さ

二分探索では、start、end、mid という 3 つの異なる変数を使用します。これら 3 つの変数は、配列インデックスのメモリ位置を指すポインターとして作成されます。このため、二分探索はスペースを非常に効率的に使用できます。反復二分探索の空間計算量は O(1) です。再帰的な実装の場合、それは O(log N) です。