【Java】再帰処理による二分探索プログラムの書き方と解説

以下は、Javaで再帰呼び出しを用いて二分探索（バイナリサーチ）を実装したサンプルプログラムです。

サンプルコード

public class Demo{
    int rec_bin_search(int my_arr[], int left, int right, int x){
        if (right >= left){
            int mid = left + (right - left) / 2;
            if (my_arr[mid] == x)
                return mid;
            if (my_arr[mid] > x)
                return rec_bin_search(my_arr, left, mid - 1, x);
            return rec_bin_search(my_arr, mid + 1, right, x);
        }
        return -1;
    }
    public static void main(String args[]){
        Demo my_object = new Demo();
        int my_arr[] = { 32, 45, 56, 78, 90, 99, 104};
        int len = my_arr.length;
        int x = 104;
        int result = my_object.rec_bin_search(my_arr, 0, len - 1, x);
        if (result == -1)
            System.out.println("The element is not present in the array");
        else
            System.out.println("The element has been found at index " + result);
    }
}

実行結果

The element has been found at index 6

コードの解説

クラス「Demo」の中に、二分探索を行うメソッド rec_bin_search を定義しています。このメソッドは、対象となる配列・探索範囲の左端（left）・右端（right）・そして探したい値（x）を引数として受け取ります。

まず探索範囲の中央インデックス mid を計算し、その位置の値と目的の値を比較します。一致していればそのインデックスを返し、中央の値が大きければ左半分を、小さければ右半分を対象として自分自身を再帰的に呼び出し、探索範囲を半分ずつ絞り込みながら処理を続けます。最終的に要素が見つからなければ -1 を返します。

main メソッドでは Demo クラスのインスタンスを生成し、配列に値を設定したうえで二分探索メソッドを呼び出しています。要素が見つかった場合はそのインデックスが表示され、見つからなかった場合は「要素が配列内に存在しない」旨のメッセージが出力されます。

注意点：二分探索にはソート済み配列が必要

二分探索は「配列が昇順にソートされている」ことを前提としたアルゴリズムです。ソートされていない配列に対しては正しく動作しないため、事前に Arrays.sort() などで並べ替えておく必要があります。

また、二分探索の時間計算量は O(log n) であり、先頭から順に調べる線形探索の O(n) と比べて、大規模なデータセットでも高速に検索できる点が大きなメリットです。