JavaScriptで二分探索を実装する方法：初心者向け徹底ガイド

JavaScriptで二分探索を書く方法

探索アルゴリズムは、プログラマーの作業を大きく効率化してくれる強力なツールです。これを使えば、数十件、数百件、さらには数千件のデータの中からも、目的の項目を素早く見つけ出すことができます。

最もよく知られている探索手法のひとつが「二分探索（バイナリサーチ）」です。このアルゴリズムは、配列の中から目的の項目を高速に見つけることができます。探索のたびに、残りの検索対象が半分に絞り込まれていくのが特徴です。

この記事では、二分探索の仕組みと基本的な考え方を解説し、その後、「反復（イテレーティブ）」と「再帰（リカーシブ）」という2つの異なるアプローチでJavaScriptによる実装方法を紹介します。

それでは、JavaScriptで二分探索アルゴリズムを作ってみましょう！

二分探索とは？

二分探索とは、ソート済み（整列済み）の配列から特定の項目を探し出すためのコンピュータサイエンスのアルゴリズムです。

探索は配列の中央から始まります。中央の要素が、探している値より「小さい」「等しい」「大きい」のどれに該当するかを判定します。

探している値が中央の値より小さければ、小さい数が集まっている配列の左半分を探索対象とします。逆に大きければ、右半分に絞り込みます。なお、二分探索が使えるのはソート済みのリストのみである点に注意してください。

二分探索は線形探索（リニアサーチ）よりもはるかに効率的です。その理由は、探索を1回行うごとに、残りの検索対象が半分に減っていくためです。

二分探索の使い方

二分探索は、コツをつかめばとてもシンプルに理解できます。

実際にコードを書く前に、まずは手順を一つずつ確認していきましょう。ここでは、リストの中から数字「9」を探す例を取り上げます。次のソート済みリストを用意しました。

2

6

8

9

10

まず、中央の値を求めて変数に代入します。中央の値は、先頭と末尾の値を足して2で割ることで計算できます。この変数を「middle（中央）」と呼びましょう。

Start（先頭）		Middle（中央）		End（末尾）
2	6	8	9	10

中央の値は「8」です。次に、この中央の値と探している値を比較します。もし中央の値が探している値と一致していれば、そこで探索は終了です。

この例では、8と9は一致しないので、探索を続けます。

次に、中央の値が9より大きいかどうかを確認します。結果は「いいえ」でした。

これは、探している値が中央の値より後ろに存在することを意味します。ソート済みリストにおいて、9は8より大きいからです。そこで、探索の開始位置を中央の値に移動します。探している値が中央の値より前に存在しないことが確定したからです。

逆に、探している値が中央の値より小さい場合は、末尾の位置を中央の値に設定します。こうすることで、リストの下半分に探索範囲を絞り込めます。

9は8より大きいため、二分探索はリストの上半分で再び実行されます。

		Start（先頭）	Middle（中央）	End（末尾）
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ループは、startがendより大きくなるまで実行され続けます。ループ内では、startとendの間の中央の値を計算します。

探している値が中央の値と一致していれば、中央のインデックスをメインプログラムに返します。探している値が中央の値より小さければ、startを「中央 + 1」に更新します。これらの比較はif文で行っています。

それ以外の場合（探している値が中央の値より大きい場合）は、endを「中央 − 1」に更新します。whileループが終了しても値が見つからなかった場合は、-1を返します。これを「ベース条件（終了条件）」と呼びます。メインプログラム側では、戻り値が-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文を使って「startがendより大きくなったか」をチェックしています。これが真であれば、指定したリストの中に目的の項目が存在しなかったことを意味するため、メインプログラムに-1を返します。

探している値が中央の値と一致していれば、中央のインデックスをメインプログラムに返します。一致せず、値が中央より大きいか小さい場合は、binarySearch関数が自分自身を呼び出して再び実行されます。これが、項目が見つかるまで（またはリスト全体を探索し終えるまで）続きます。

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

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

新たに2つの引数「start」と「end」の値を渡す必要があります。startは0、endは「リストの長さ − 1」を指定します。

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

9 has been found at position 3.

二分探索は成功しました！ 基本的なアルゴリズムは反復版とまったく同じです。違いは、関数が自分自身を呼び出し続けることで探索を実行する点です。項目が見つかるか、リスト全体の探索が完了するか、どちらか先に起こった時点で処理が終了します。

まとめ

二分探索を使えば、リストの中から目的の項目を簡単に見つけられます。探索を実行するたびに残りの検索対象が半分に絞り込まれるため、線形探索よりもはるかに効率的です。

これで、あなたもプロのようにJavaScriptで二分探索を実装できるはずです！