【Java】二分探索の実装方法を徹底解説：反復法と再帰法のサンプルコード付き

Javaで二分探索アルゴリズムを実装する方法

コンピュータは、人間のように柔軟に検索を行うことができません。人間は状況に応じて探し方を変えられますが、コンピュータには特定のアイテムを見つけるための明確な手順を与える必要があります。そこで役立つのが、標準的な探索アルゴリズムです。

二分探索（バイナリサーチ）は標準的な探索アルゴリズムの一例で、ソート済みの配列から特定の要素を見つけるために使われます。このガイドでは、二分探索とは何か、どのような仕組みで動作するのか、そしてJavaでどのように実装するのかを解説します。反復法（イテレーティブ）と再帰法（リカーシブ）という2つのアプローチによる実装例も紹介します。

それでは始めましょう！

二分探索とは？

二分探索は、ソート済み配列の中から特定の要素の位置を見つけ出す探索アルゴリズムです。

二分探索では、まずリストを半分に分割します。次に、中央の値と探索したい値を比較します。

探索対象の値が中央の値より小さければ、リストの下半分に対して同じ処理を繰り返します。大きければ、上半分に対して同じ処理を繰り返します。

二分探索は、線形探索（リニアサーチ）と呼ばれる一般的な探索方法よりも効率的です。これは、探索のたびに検索対象となる要素数が半分に減っていくためです。

なお、二分探索を実行できるのはソート済みのリストだけです。そのため、リストがまだソートされていない場合は、二分探索を実行する前にソートアルゴリズムで並べ替えておく必要があります。

二分探索の仕組み

二分探索の実装方法には、「反復法」と「再帰法」の2つがあります。

反復法による二分探索は、ループ処理を使ってリスト内のアイテムを検索する方法です。一方、再帰法による二分探索は、関数が自分自身を何度も呼び出すことでリスト内のアイテムを検索します。再帰的な二分探索では「分割統治法」のアプローチが用いられます。

再帰について詳しく学びたい方は、Javaの再帰に関するガイドも参考にしてください。

どちらのアプローチを選んでも、二分探索を実装する際の基本的なアルゴリズムは同じです。

次のリストを例に考えてみましょう。

6

7

8

9

10

このリストから「7」を検索することにします。まず、リストの最小位置と最大位置を表す2つのポインタを設定します。

Low				High
6	7	8	9	10

次に、配列の中央の要素を見つけます。これには「(low + high) / 2」という式を使います。この場合、中央の要素は8です。

アルゴリズムは、中央の要素が探索対象の値と一致しているかどうかを比較します。一致していれば探索は終了です。ここでは7を探していますが、8とは一致しないため、探索は続行されます。

続いて、アルゴリズムは探索対象の値が中央の値より大きいかどうかを比較します。大きければ、リストの上半分に対して最初から探索をやり直します。これは「low = middle_number + 1」と設定することで行われます。そうでなければ、リストの下半分に対して探索をやり直します。

この例では、探索対象の7は中央の値8より大きくありません。つまり、アルゴリズムはリストの下半分を探索することになります。これには「high = middle_number - 1」と設定します。

Low	Middle	High
6	7	8	9	10

ここで、アルゴリズムは再度探索を繰り返します。中央の値7と探索対象の値を比較すると、探していたのはまさに7なので、探索アルゴリズムは停止します。リスト内の7の位置が見つかりました！

Javaで二分探索を実装する方法

理論はひと通り説明したので、あとは実際に実装するだけです。自分でリストを検索することと、検索を自動的に行うアルゴリズムをコーディングすることは、まったく別の話です。

まずは、反復法を使ってJavaの二分探索を実装するプログラムを書いてみましょう。

反復法（イテレーティブ）

リスト内のアイテムを検索するsearchItemsという関数を定義してみましょう。

class BinarySearch {
	int searchItems(int array[], int searchingFor, int low, int high) {
		while (low <= high) {
			int middle = low + (high - low) / 2;

			if (array[middle] == searchingFor) {
				return middle;
			} else if (array[middle] < searchingFor) {
				low = middle + 1;
			} else {
				high = middle - 1;
			}
		}
		return -1;
	}
}

この関数は、二分探索を使ってリスト内のアイテムを検索します。

この関数は4つの引数を受け取ります。検索対象のリスト（array）、探したいアイテム（searchingFor）、最小値（low）、最大値（high）です。

関数内ではwhileループを宣言しています。「low」の値が「high」以下である限り、ループが実行されます。

whileループでは、まず中央の値を計算し、その位置にある値が探索対象と一致するかどうかを確認します。

一致していれば、その値がメインプログラムに返されます。一致しない場合は、中央の位置にある値が探索対象より小さいかどうかを確認します。小さければ、新しいlowの値が設定されます。

それ以外の場合は、新しいhighの値が設定され、リストの上半分に対して再度探索が行われます。

アイテムが見つからなかった場合は、-1が返されます。この値は後ほど、メインプログラムに「アイテムが見つからなかった」ことを伝えるために使います。

現時点ではメインプログラムを書いていないため、このコードはまだ何もしません。BinarySearchクラスのsearchItems()関数の下に、次のコードを追加してください。

public static void main(String args[]) {
		BinarySearch newSearch = new BinarySearch();

		int listToSearch[] = { 6, 7, 8, 9, 10 };
		int listLength = listToSearch.length;
		int numberToFind = 7;

		int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1);

		if (findNumber != -1) {
			System.out.println(numberToFind + " was found at index position " + findNumber + ".");
		} else {
			System.out.println(numberToFind + " was not found in the list.");
		}
	}

それでは、コードを実行して結果を確認してみましょう。

7 was found at index position 1.

数字の位置が見つかりました！

メインプログラムでは、まずBinarySearchクラスのインスタンスを初期化します。これは後ほどプログラム内で探索を開始するために使用します。次に、3つの変数を定義します。

• listToSearch：検索対象となるリスト
• listLength：リストの長さ
• numberToFind：リスト内で探したい数字

これらの変数を定義したら、先ほど宣言したsearchItems()関数を使ってリスト内の数字を検索します。この関数の戻り値は変数「findNumber」に代入されます。

findNumberが-1と等しくない場合（つまり数字が見つかった場合）、探索していたアイテムのインデックス位置がコンソールに出力されます。それ以外の場合は、数字が見つからなかったことを伝えるメッセージがコンソールに出力されます。

再帰法（リカーシブ）

二分探索は、再帰的なアプローチでも実装できます。これは、指定されたアイテムが見つかるまで関数が自分自身を呼び出し続ける方法です。

まず、二分探索を再帰的に実行する関数を定義しましょう。

class BinarySearch {
	int searchItems(int array[], int searchingFor, int low, int high) {
		if (high >= low) {
			int middle = low + (high - low) / 2;
	
			if (array[middle] == searchingFor) {
				return middle;
			} else if (array[middle] < searchingFor) {
				searchItems(array, searchingFor, middle + 1, high);
			} else {
				searchItems(array, searchingFor, low, middle - 1);
			}
		}
		return -1;
	}
}

この関数は、先ほどとは異なる方法で二分探索を実装しています。whileループの代わりにif文を使い、highの値がlow以上であるかどうかを確認します。

この条件がtrueと評価されれば探索が開始されます。そうでなければ-1が返され、指定されたアイテムがリスト内に見つからなかったことがプログラムに伝わります。

if文の中では、中央の値が探索対象と一致しているかどうかを確認します。一致していれば、その値がメインプログラムに返されます。

条件がtrueにならない場合は、中央の位置にある値が探索対象より小さいかどうかを確認します。小さければ、searchItems()メソッドが再度実行されますが、今回はlowの値が中央の値+1に設定されます。これにより、検索対象の要素数が半分になります。

それ以外の場合は、searchItems()が再度実行され、highの値が中央の値-1に設定されます。これにより、探索範囲をリストの左半分だけに絞り込むことができます。

先ほど書いた同じmain関数を使って、このコードをテストできます。コードを実行するとどうなるか見てみましょう。

7 was found at index position 1.

またアイテムが見つかりました！今回は、反復法ではなく再帰法を使って数字を検索しました。

計算量の分析

二分探索アルゴリズムの最良ケースの計算量はO(1)です。これは、アルゴリズムが最初に比較した要素がたまたま探索対象だった場合に発生します。

二分探索アルゴリズムの平均計算量と最悪計算量はO(log n)です。つまり、ほとんどの場合および最悪の場合において、アルゴリズムの速度はリスト内の要素数に応じて対数的に遅くなります。

まとめ

二分探索は、ソート済みリスト内の要素の位置を見つけるために使われるアルゴリズムです。二分探索では、配列の一部の中央にある要素と、探索対象の値を比較します。

二分探索は線形探索よりも効率的です。これは、探索が実行されるたびに、検索が必要な値の数が半分になるためです。

これで、あなたもプロのプログラマーのようにJavaで二分探索を実装できるようになりました。