Java による二分探索

はじめに

二分探索は、ソート済み配列内の値を見つけるために使用される効率的な探索アルゴリズムです。線形探索よりも高速であり、各反復ごとに配列の半分を除外するためです。この実験では、Java で二分探索アルゴリズムを実装する手順を学びます。

Skills Graph

ソート済み配列を作成する

二分探索アルゴリズムにはソート済み配列が必要ですので、まずソート済み配列を作成します。

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() についても学びました。ソート済み配列を作成し、その中の要素を検索するためにさまざまなメソッドを使用しました。