はじめに: 二分探索は「半分ずつ減らす」探索アルゴリズム
前回の記事では、配列を先頭から順番に調べる線形探索をJavaScriptで実装しました。線形探索は分かりやすい方法ですが、データが増えると、最悪の場合はすべての要素を確認する必要があります。
そこで登場するのが二分探索です。
二分探索は、整列済みのデータに対して、中央の値を見ながら探索範囲を半分ずつ減らしていく方法です。先頭から1つずつ見るのではなく、「目的の値は左側にあるのか、右側にあるのか」を判断して、候補を一気に絞り込みます。
基本情報処理技術者試験でも、二分探索はアルゴリズムや計算量の理解につながる重要なテーマです。この記事では、JavaScriptで二分探索を実装しながら、探索範囲の変化と O(log n) の考え方を確認していきます。
二分探索とは何か
二分探索とは、整列済みの配列から目的の値を探す探索方法です。
たとえば、次のように小さい順に並んだ配列があるとします。
[3, 8, 12, 21, 35, 42, 57]ここから 35 を探す場合、まず中央の値を見ます。この配列では中央付近の値は 21 です。探したい 35 は 21 より大きいので、左側の 3, 8, 12 は候補から外せます。
次に、右側の 35, 42, 57 の中央を見ます。そこで 42 を見た場合、探したい 35 は 42 より小さいので、今度は左側に絞れます。こうして範囲を半分ずつ狭めていきます。
二分探索で大切なのは、データが整列されていることです。並び順がばらばらだと、中央の値を見ても「左側にある」「右側にある」と判断できません。二分探索は速い方法ですが、整列済みであることが前提です。
線形探索との違い
線形探索と二分探索の違いは、調べ方にあります。
線形探索は、先頭から順番に要素を確認します。データが整列されていなくても使える一方で、目的の値が最後にある場合や存在しない場合は、すべての要素を見る必要があります。
二分探索は、中央の値を見て、探索範囲を半分に絞ります。整列済みである必要はありますが、データ数が多いほど効率の良さが見えやすくなります。
たとえば1000個のデータから探す場合、線形探索では最悪1000回近く確認する可能性があります。二分探索では、範囲を半分、さらに半分と減らしていくため、確認回数はずっと少なくなります。
つまり、線形探索は「準備が少なくて分かりやすい方法」、二分探索は「整列済みデータを効率よく探す方法」と整理できます。
JavaScriptで二分探索を実装する
JavaScriptで二分探索を書くときは、探索範囲の左端と右端を表す変数を使います。
left: 探索範囲の左端right: 探索範囲の右端middle: 探索範囲の中央
中央の値と目的の値を比べて、探索範囲を更新していきます。
function binarySearch(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (array[middle] === target) {
return middle;
}
if (array[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
const numbers = [3, 8, 12, 21, 35, 42, 57];
console.log(binarySearch(numbers, 35));
console.log(binarySearch(numbers, 10));array[middle] === target なら、目的の値が見つかったので middle を返します。
中央の値が目的の値より小さい場合、目的の値は右側にあるはずです。そのため、left = middle + 1 として左端を更新します。逆に中央の値が目的の値より大きい場合は、右端を right = middle - 1 に更新します。
最後まで見つからなければ -1 を返します。この戻り値は、線形探索の記事で実装した関数と同じ形にしています。
探索範囲がどう変わるかを追ってみる
二分探索は、left、right、middle の動きを追うと理解しやすくなります。処理の途中で値を表示してみましょう。
function binarySearchWithLog(array, target) {
let left = 0;
let right = array.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
console.log({ left, middle, right, value: array[middle] });
if (array[middle] === target) {
return middle;
}
if (array[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
const numbers = [3, 8, 12, 21, 35, 42, 57];
console.log(binarySearchWithLog(numbers, 35));このコードを実行すると、探索範囲の左端、中央、右端がどのように変わるかを確認できます。
科目Bのアルゴリズム問題では、このような変数の変化を追う力が大切です。特に、中央の値を見たあとに left を動かすのか、right を動かすのかを読み間違えないようにしましょう。
二分探索の計算量を理解する
二分探索では、1回比較するたびに探索範囲がほぼ半分になります。
たとえば、データが16個あっても、1回比較すると候補は約8個、次に約4個、次に約2個と減っていきます。線形探索のように1つずつ減るのではなく、一気に候補を減らせるのが特徴です。
このような計算量は、オーダ記法で O(log n) と表します。
基本情報の学習では、まず「データ数が増えても、確認回数はゆっくり増える」と理解するとよいです。線形探索の O(n) はデータ数に比例して確認回数が増えますが、二分探索の O(log n) はそれよりも増え方が小さくなります。
ただし、二分探索を使うにはデータが整列済みである必要があります。整列するための処理が別に必要な場合もあるので、いつでも二分探索が最適とは限りません。
試験ではどう問われるか
基本情報処理技術者試験では、二分探索は処理のトレースや計算量の問題として出てきやすいテーマです。
特に、次の点を押さえておくと整理しやすくなります。
- 配列の中央を求める
- 中央の値と目的の値を比較する
leftとrightを更新する- 見つかった場合は探索を終了する
left <= rightの間だけ探索を続ける- 最悪の場合の計算量は
O(log n) - 整列済みデータが前提である
線形探索との違いもよく問われます。線形探索は未整列でも使えますが、二分探索は整列済みでなければ使えません。この前提条件を見落とさないことが重要です。
実務ではどう使われるか
実務では、二分探索を毎回自分で書く場面はそれほど多くありません。多くの場合、データベース、ライブラリ、言語やフレームワークの機能が検索処理を引き受けてくれます。
それでも、二分探索の考え方を知っておく意味はあります。
大量のデータを扱うとき、探し方やデータの持ち方によって処理速度は大きく変わります。ソート済みのデータを使えるなら、中央を見て範囲を減らすという考え方が役立つ場面があります。
また、検索UIや候補の絞り込み、ページング、範囲検索などを考えるときにも、「全部を順に見るのか」「候補を効率よく減らせるのか」という視点は大切です。
アルゴリズムを知っていると、コードをただ動かすだけでなく、データが増えたときにどこが重くなりそうかを考えやすくなります。
まとめ: 二分探索は整列済みデータを効率よく探す方法
二分探索は、整列済みのデータに対して、中央の値を見ながら探索範囲を半分ずつ減らしていくアルゴリズムです。
線形探索は先頭から順番に調べますが、二分探索は候補を一気に減らせるため、データ数が多いほど効率の差が見えやすくなります。計算量は O(log n) です。
ただし、二分探索は整列済みデータが前提です。使える条件と効率の良さをセットで理解しておくことが大切です。
次に学ぶなら、データを整列するためのソートや、別の探し方としてハッシュ表に進むと、アルゴリズムの選び方がさらに見えやすくなります。
コメント