二分探索JavaScript：ガイド

JavaScriptでバイナリ検索をコーディングする方法

アルゴリズムを検索すると、プログラマーとしての生活がとても楽になります。そうすることで、数十、数百、または数千のアイテムのデータセット内で特定のアイテムを簡単に見つけることができます。

最も人気のある検索形式の1つは、二分探索です。この検索で​​は、配列内のアイテムがすばやく見つかります。検索でアイテムを検索するたびに、検索される残りのアイテムの数が半分になります。

このガイドでは、二分探索とは何か、そしてそれらがどのように機能するかについて説明します。次に、反復と再帰の2つの異なるアプローチを使用してバイナリ検索を実装します。

JavaScriptで二分探索アルゴリズムを構築しましょう！

二分探索とは何ですか？

二分探索は、ソートされた配列内の項目を検索するコンピューターサイエンスアルゴリズムです。

配列の中央から開始し、中央の項目が検索対象の数より少ないか、等しいか、多いかをチェックします。

数値が小さい場合、アルゴリズムは配列の左半分を検索し続けることを認識します。ここで、数値は小さくなります。数値が大きい場合、アルゴリズムは配列の右半分に焦点を合わせます。バイナリ検索は、ソートされたリストでのみ機能します。

二分探索は線形探索よりも効率的です。これは、検索が行われるたびに、リスト内の検索に残っているアイテムの数が半分になるためです。

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

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

二分探索の使用方法

二分探索は、一度コツをつかめば簡単に理解できます。

二分探索アルゴリズムを実装する前に、ステップバイステップで見ていきましょう。リストから「9」という数字を見つけます。ソートされたリストから始めましょう：

2

6

8

9

10

まず、真ん中の数字を見つけて変数に割り当てる必要があります。これは、最初と最後の数値の合計を計算し、それを2で割ることによって求められます。この変数を「中間」と呼びます。

開始		中		終了
2	6	8	9	10

8は私たちの真ん中の数です。次に、真ん中の数字を検索している数字と比較できます。真ん中の数字が私たちが探しているものと等しい場合、私たちの検索は停止する可能性があります。

この例では、8は9と等しくありません。検索は続行されます。

次に、中間の数値が9より大きいかどうかを比較する必要があります。そうではありません。

これは、検索する番号が中央の番号の後になければならないことを示しています。ソートされたリストでは、9は8より大きいです。開始番号を中央の番号と等しくなるように設定します。これは、検索している番号が中央の番号の前に来ていないことがわかっているためです。

検索する番号が小さい場合は、終了番号を中央の番号と等しくなるように設定します。数字が中央の数字よりも小さいため、リストの下半分に検索を集中させることができます。

9は8より大きいため、バイナリ検索はリストの上半分で再び繰り返されます。

		開始	中	終了
2	6	8	9	10

再び真ん中の数字を見つけます。これは9です。9を検索している数と比較できます。 9は、検索対象の数と同じです。

これは、検索が停止する可能性があることを意味します。リストで9番を見つけることに成功しました！

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

バイナリ検索は、反復的または再帰的なアプローチを使用して実装できます。

反復二分探索

反復二分探索では、whileループを使用して、リスト内の項目を検索します。このループは、アイテムがリストで見つかるまで、またはリストが検索されるまで実行されます。

バイナリ検索を実行する関数を作成することから始めましょう。

function binarySearch(array, numberToFind) {
	let start = 0;
	let end = array.length - 1;

	while (start <= end) {
		let middle = Math.floor((start + end) / 2);

		if (array[middle] === numberToFind) {
			return middle;
		} else if (array[middle] < numberToFind) {
			start = middle + 1;
		} else {
			end = middle - 1;
		}
	}

	return -1;
}

まず、startとendの2つの変数を定義します。これらは、検索で使用している最高値と最低値を追跡します。開始番号が終了番号より大きくなるまで実行されるwhileループを使用します。このループは、リストの開始と終了の中間の数値を計算します。

検索対象の数が真ん中の数と等しい場合、真ん中の数がメインプログラムに返されます。数値が小さい場合、開始値は中央の数値に1を加えた値に等しくなるように設定されます。これらの比較は、ifステートメントを使用して実行されます。

それ以外の場合、終了番号は中央の番号から1を引いた値に等しくなるように設定されます。 whileループの実行後に番号が見つからない場合は、-1が返されます。これを基本条件と呼びます。メインプログラムでは、返される数が-1に等しいかどうかを確認します。もしそうなら、それは私たちの番号が見つからなかったことを意味します。

私たちの機能はまだ機能していません。それを呼び出すメインプログラムを作成する必要があります：

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind);

if (findNumber !== -1) {
	console.log(`${toFind} has been found at position ${findNumber}.`);
} else {
	console.log(`${toFind} has not been found.`);
}

検索する番号のリストと、リストで検索する番号を定義しました。次に、binarySearch関数を呼び出しました。これで検索が実行されます。検索では、-1または検索対象のアイテムの位置が返されます。

-1は、アイテムが見つからなかったことを示します。アイテムが見つからない場合は、elseの内容 ステートメントが実行されます。それ以外の場合、ifの内容 ステートメントが実行されます。

コードを実行してみましょう：

9 has been found at position 3.

これは、検索が成功したことを示しています！

再帰的二分探索

再帰的な二分探索は、反復的な探索よりも洗練されていると見なされます。これは、バイナリ検索がリストに対して同じ操作を繰り返し実行するためです。この動作は、再帰アルゴリズムを使用して実装できます。

新しいJavaScriptファイルを開き、次のコードを貼り付けます：

function binarySearch(array, numberToFind, start, end) {
	if (start => end) {
		return -1;
	}

	let middle = Math.floor((start + end) / 2);

	if (array[middle] === numberToFind) {
		return middle;
	} else if (array[middle] < numberToFind) {
		return binarySearch(array, numberToFind, middle + 1, end);
	} else {
		return binarySearch(array, numberToFind, start, middle - 1);
	}
}

このコードは、最初の検索と同じ比較を行います。中央の数値が、検索対象の数値と等しいか、大きいか、または小さいかをチェックします。

関数の開始時に、ifステートメントを使用して、開始番号が終了番号より大きいかどうかを確認しました。そうである場合、これは、指定したリストにアイテムが見つからなかったことを意味します。この場合、メインプログラムに-1を返します。

探している番号が真ん中の数字と同じである場合、真ん中の数字はメインプログラムに返されます。探している数値が中央の数値よりも大きいか小さい場合、binarySearch関数が再度実行されます。これは、アイテムが見つかるまで続きます。

この関数を実行するには、メインプログラムに変更を加える必要があります。

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1);
… 

「start」と「end」の値という2つの追加パラメーターを渡す必要があります。 「start」の値は0に等しくなります。「end」の値はリストの長さから1を引いたものに等しくなります。

コードを実行して、何が起こるか見てみましょう：

9 has been found at position 3.

二分探索は成功しました！これは、反復アプローチと同じ基本的なアルゴリズムを使用します。違いは、バイナリ検索は、アイテムが見つかるまで、またはリストが完全に検索されるまで、どちらか早い方で自分自身を呼び出す関数を使用して実行されることです。

結論

バイナリ検索を使用すると、リスト内のアイテムを簡単に見つけることができます。検索が実行されるたびに、リスト内で検索するために残されたアイテムの数が半分に減ります。これにより、線形検索よりもバイナリ検索の方が効率的です。

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