二分探索Java：ガイド

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

コンピューターは、人間のようにアイテムを検索しません。人間は何かを見つけるためのアプローチを変えることができますが、コンピューターには特定のアイテムを見つける方法について特定の指示を与える必要があります。そこで、標準のアルゴリズムが役立ちます。

二分探索は、標準的なアルゴリズムの一例です。これらは、ソートされたアイテムの配列内の要素を見つけるために使用されます。このガイドでは、バイナリ検索とは何か、それらがどのように機能するか、およびJavaでそれらを実装する方法について説明します。二分探索の2つの例を見ていきます。1つは再帰的アプローチを使用し、もう1つは反復的アプローチを使用します。

始めましょう！

二分探索とは何ですか？

二分探索は、ソートされた配列内の要素の位置を見つける検索アルゴリズムです。

二分探索は、リストを半分に分割することから始まります。次に、検索では、中央の数値がアルゴリズムが検索している数値と比較されます。

数値が中央の数値よりも小さい場合、このプロセスがリストの下半分に対して繰り返されます。それ以外の場合は、このプロセスがリストの上半分に対して繰り返されます。

バイナリ検索は、別の一般的なタイプの検索である線形検索よりも効率的です。これは、アルゴリズムがアイテムを検索するたびに、検索するアイテムの数が2分の1に減少するためです。

バイナリ検索は、ソートされたアイテムのリストに対してのみ実行できます。つまり、並べ替えられたリストがまだない場合は、バイナリ検索を実行する前に、並べ替えアルゴリズムを使用してリストを並べ替える必要があります。

参加者の81％は、ブートキャンプに参加した後、自分たちの技術的な仕事の見通しについてより自信を持っていると述べました。今日のブートキャンプにマッチしましょう。

平均的なブートキャンプの卒業生は、ブートキャンプの開始から最初の仕事を見つけるまで、キャリアの移行に6か月も費やしませんでした。

二分探索はどのように機能しますか？

二分探索は、反復的または再帰的の2つの方法で実装できます。

反復二分探索は、ループを使用してリスト内の項目を検索するものです。再帰的バイナリ検索では、リスト内のアイテムを見つけるために何度も自分自身を呼び出す関数を使用します。再帰的二分探索では、分割統治法を使用してアイテムを検索します。

再帰について詳しくは、Java再帰ガイドをご覧ください。

二分探索を実装するための一般的なアルゴリズムは、どのアプローチを使用する場合でも同じです。

次のリストを検討してください。

6

7

8

9

10

リストで7番を検索します。まず、リストの最低位置と最高位置を表す2つのポインターを設定します。

低				高
6	7	8	9	10

次に、配列内の中央の要素を見つける必要があります。これは、式（low + high）/ 2を使用して行うことができます。この場合、中央の要素は8です。

私たちのアルゴリズムは、真ん中の要素が検索対象の要素と等しいかどうかを比較します。数が等しい場合、検索を停止できます。 8と等しくない7という数字を探しているので、検索を続けます。

私たちのアルゴリズムは、検索している数が中央の数より大きいかどうかを比較します。それが大きい場合は、リストの上半分から検索が最初からやり直されます。これは、lowをlow =middle_number + 1に等しく設定することによって実行されます。それ以外の場合、検索はリストの下半分で再開されます。

7（検索している数値）は8（中央の数値）以下です。これは、アルゴリズムがリストの下半分を検索することを意味します。これを行うには、「high」値をhigh =middle_number –1に設定します。

低	中	高
6	7	8	9	10

これで、アルゴリズムが検索を繰り返します。真ん中の数字の7を、検索している数字と比較します。番号7を探しているので、検索アルゴリズムは停止します。リストで7位になりました！

Javaバイナリ検索を実装する方法

理論は完成したので、あとは検索を実装するだけです。それは、自分たちでリストを調べて検索することの1つです。私たちを検索するアルゴリズムをコーディングすることは、まったく別のことです。

まず、反復法を使用して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;
	}
}

この関数は、バイナリ検索を使用してアイテムのリストを検索します。

この関数は、検索対象のリスト（array）、検索対象のアイテム（searchingFor）、低い数値（low）、および高い数値（high）の4つのパラメーターを受け入れます。

関数内で、whileループを宣言しました。 「low」の値が「high」以下の場合、ループが実行されます。

whileループは、真ん中の数値を計算することから始まります。次に、その位置の値が検索対象の値と等しいかどうかを確認します。

これらの数値が等しい場合、その値はメインプログラムに返されます。そうでない場合、プログラムは中央の位置の値が検索対象の値よりも小さいかどうかをチェックします。そうである場合、新しい低い値が設定されます。

それ以外の場合は、新しい高い値が設定され、リストがリストの上半分を再度検索できるようになります。

アイテムが見つからない場合は、-1が返されます。これを使用して、リストアイテムがすぐに見つからないことをメインプログラムに通知します。

メインプログラムを作成していないため、コードはまだ何もしていません。 searchItems()の下に次のコードを追加します BinarySearchクラスの関数：

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.

We've found the position of our number!

メインプログラムは、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を使用します 高い数値が低い数値以下であるかどうかを確認するステートメント。

このステートメントがtrueと評価された場合、検索が開始されます。それ以外の場合は、-1が返されます。これは、指定された項目がリストに見つからなかったことをプログラムに通知します。

ifの内部 ステートメントでは、真ん中の数値の値が検索対象の値と等しいかどうかを確認します。そうである場合は、その番号をメインプログラムに戻します。

このステートメントがtrueと評価されない場合、プログラムは中央の位置の数値が検索対象の数値よりも少ないかどうかを確認します。そうである場合、searchItems() メソッドが再度実行されますが、今回は、小さい数値が中間の数値より1大きい値になります。これにより、リストで検索する必要のあるアイテムの数が2で除算されます。

それ以外の場合は、searchItems() が再度実行され、最大数の値が中間数から1を引いた値に等しくなります。これは、リストの左半分にのみ検索を絞り込むことができることを意味します。

以前に作成したのと同じmain関数を使用して、コードをテストできます。コードを実行するとどうなるか見てみましょう：

7 was found at index position 1.

私たちのアイテムが再び見つかりました！今回は、反復的な番号ではなく、再帰的なアプローチを使用して番号を見つけました。

複雑さの分析

二分探索アルゴリズムのベストケースの複雑さはO（1）です。これは、アルゴリズムによって比較される最初のアイテムが検索されているアイテムである場合に発生します。

二分探索アルゴリズムの平均および最悪の場合の複雑さはO（log n）です。これは、ほとんどの場合、最悪の場合、リストが検索する必要のあるアイテムの数に応じて、アルゴリズムの速度が対数的に遅くなることを意味します。

結論

二分探索は、ソートされたリスト内の要素の位置を見つけるために使用されます。二分探索では、配列の一部の中央にある項目を、アルゴリズムが検索している数と比較します。

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

これで、エキスパートプログラマーのようにJavaでバイナリ検索を実装する準備が整いました。