こんにちは、フルスタックエンジニアのryuです。
今回の記事では、基本情報技術者試験の過去問を使いながら、二分探索の仕組みについて解説します。
二分探索は、整列されたデータの中から目的の値を探すアルゴリズムです。名前だけを見ると難しそうですが、やっていることは「真ん中を見る→不要な半分を捨てる」を繰り返しているだけです。
基本情報技術者試験では、アルゴリズムの名前を覚えるだけではなく、擬似言語を読んで処理の流れを追えるようにしておくことが大切です。
この記事では、まず過去問を解き、そのあとに二分探索がどのように動くのかを、配列とトレース表を使って順番に確認していきます。
二分探索に関する記述のうち適切なものはどれか¶
今回はこちらの問題です。
二分探索に関する記述のうち、適切なものはどれか。
ア：二分探索するデータ列は整列されている必要がある。 イ：二分探索は線形探索より常に速く探索できる。 ウ：二分探索は探索をデータ列の先頭から開始する。 エ：n個のデータの探索に要する比較回数は、nlog2nに比例する。 出典：平成26年秋期 問6
答えは、アの「二分探索するデータ列は整列されている必要がある」です。
なぜアが正解なのか、二分探索の動きを確認しながら見ていきましょう。
二分探索とは？¶
二分探索とは、整列済みのデータから目的の値を探すアルゴリズムです。
例えば、次のように小さい順に並んだデータがあるとします。
10 20 30 40 50 60 70 80 90
この中から70を探してみましょう。
線形探索であれば、基本的には先頭から順番に確認します。
10 → 違う
20 → 違う
30 → 違う
40 → 違う
50 → 違う
60 → 違う
70 → 見つかった
この場合、7回確認しています。
一方、二分探索では最初に真ん中を確認します。
10 20 30 40 [50] 60 70 80 90
真ん中は50です。
探している70は50より大きいため、50より左側にある、
10 20 30 40
は、もう確認する必要がありません。
探索する範囲を右半分に絞ります。
60 [70] 80 90
次に中央付近の値を確認すると70が見つかります。
このように、1回比較するたびに探す範囲をおおよそ半分にできるのが二分探索です。
なぜ二分探索は整列されている必要があるの？¶
今回の問題で一番大切なのがここです。
二分探索では、中央の値と目的の値を比較して、
「目的の値は左側にある」 「目的の値は右側にある」
と判断します。
この判断ができるのは、データが昇順や降順に並んでいるからです。
例えば、
10 20 30 40 50 60 70 80 90
で中央の50を見たとき、目的の値が70なら、
「70は50より大きい。だから50より左側にはない」
と判断できます。
しかし、次のようにバラバラに並んでいたらどうでしょうか。
80 10 40 90 50 20 70 30 60
中央に50があっても、50より大きい値が左右の両方にあります。
これでは、半分を捨てることができません。
そのため、二分探索を行うには、事前にデータが整列されている必要があります。
ここは基本情報技術者試験でも重要なポイントなので覚えておきましょう。
二分探索の処理を擬似言語で見てみよう¶
現在の基本情報技術者試験の科目Bでは、プログラムは擬似言語を使って出題されます。
そのため、二分探索も「意味を知っている」だけではなく、擬似言語になったときに処理を追えるようにしておくことが大切です。
説明用に、二分探索の処理を簡単な擬似言語で表してみます。
data ← {10, 20, 30, 40, 50, 60, 70, 80, 90}
target ← 70
left ← 1
right ← 9
while (left ≦ right)
mid ← (left + right) div 2
if (data[mid] = target)
「見つかった」
繰返しを終了する
elseif (data[mid] < target)
left ← mid + 1
else
right ← mid - 1
endif
endwhile
最初は少し長く見えるかもしれません。
ただ、見るべき変数は主に次の4つです。
left：探索範囲の左端right：探索範囲の右端mid：現在確認する中央の位置target：探している値
全部を一度に追うのではなく、この4つがどう変わるのかを確認すると読みやすくなります。
二分探索をトレースしてみよう¶
先ほどの例で、70を探してみます。
最初は、
left = 1
right = 9
です。
中央の位置を計算します。
mid = (1 + 9) div 2
= 5
5番目の値は50です。
data[5] = 50
探している値は70なので、
50 < 70
となります。
つまり、目的の値は中央より右側にあります。
そこで、
left ← mid + 1
を実行します。
left = 6
になりました。
次は、
left = 6
right = 9
なので、
mid = (6 + 9) div 2
となり、中央付近を確認して探索範囲をさらに絞っていきます。
トレースすると、次のようなイメージです。
| 回数 | left | right | mid | 確認する値 | 判断 |
|---|---|---|---|---|---|
| 1 | 1 | 9 | 5 | 50 | 70の方が大きいので右側へ |
| 2 | 6 | 9 | 7 | 70 | 見つかった |
9個のデータがありますが、今回は2回の比較で目的の値を見つけられました。
科目Bの擬似言語問題では、このように変数の値を表にして追う方法がかなり有効です。
頭の中だけで処理しようとすると、left、right、midのどれが変わったのか分からなくなります。
最初のうちは面倒でも、表を書いて確認するのがおすすめです。
線形探索と二分探索の違い¶
二分探索と一緒に覚えておきたいのが線形探索です。
線形探索は、基本的に先頭から順番にデータを確認していきます。
例えば、
10 20 30 40 50 60 70 80 90
から70を探す場合、
10 → 20 → 30 → 40 → 50 → 60 → 70
というように確認します。
二分探索では、
50 → 70
のように、不要な範囲を捨てながら探します。
違いを簡単にまとめると次のとおりです。
| 線形探索 | 二分探索 | |
|---|---|---|
| 探し方 | 先頭から順番に調べる | 中央から範囲を半分ずつ絞る |
| 整列 | 必要ない | 必要 |
| 探索の計算量 | O(n) | O(log n) |
| 実装 | 比較的簡単 | 探索範囲の管理が必要 |
ここで大切なのは、「二分探索の方が常に優れている」と考えないことです。
データが整列されていない場合、二分探索を行うためには先に並べ替える必要があります。
また、目的の値が先頭にあるなら、線形探索では1回の比較で見つかることもあります。
用途によって使い分けることが大切です。
各選択肢を詳しく確認しよう¶
ここで、最初の問題へ戻ります。
ア：二分探索するデータ列は整列されている必要がある¶
これは正解です。
二分探索では中央の値を確認し、目的の値が右側にあるのか左側にあるのかを判断します。
そのため、データがあらかじめ昇順または降順に整列されている必要があります。
イ：二分探索は線形探索より常に速く探索できる¶
これは誤りです。
「常に」という部分に注意してください。
例えば、探している値がデータ列の先頭にあれば、線形探索では1回目で見つかります。
また、データが整列されていなければ、二分探索を利用する前に整列する処理が必要になることもあります。
二分探索は大きな整列済みデータを探索するときに効率のよい方法ですが、「どんな場合でも必ず線形探索より速い」というわけではありません。
ウ：二分探索は探索をデータ列の先頭から開始する¶
これは誤りです。
先頭から順番に確認するのは線形探索です。
二分探索では、まず探索範囲の中央付近を確認します。
この違いはセットで覚えておきましょう。
エ：n個のデータの探索に要する比較回数はnlog2nに比例する¶
これも誤りです。
二分探索では、比較するたびに探索範囲をおおよそ半分にしていきます。
そのため、探索に必要な比較回数はlog2nに比例し、計算量ではO(log n)と表します。
O(n log n)は、マージソートやヒープソートなど、一部の整列アルゴリズムで見かける計算量です。
「探索」と「整列」の計算量が混ざらないように注意しましょう。
二分探索でよくある間違い¶
二分探索の擬似言語を読むときは、いくつか間違えやすいポイントがあります。
leftとrightの更新方向を逆にする¶
例えば、
data[mid] < target
であれば、中央の値より目的の値の方が大きいので、右側を探します。
そのため、
left ← mid + 1
です。
ここを、
right ← mid - 1
としてしまうと、目的の値がある側を捨ててしまいます。
「どちらの変数を更新するのか」を暗記するのではなく、実際の配列を見ながら考えるのがおすすめです。
midそのものを残してしまう¶
探索範囲を更新するとき、
left ← mid + 1
や、
right ← mid - 1
とするのにも理由があります。
中央のdata[mid]はすでに確認済みです。
そのため、次の探索範囲にmidを残す必要はありません。
この+1や-1を見落とすと、同じ場所を繰り返し確認してしまうことがあります。
配列の添字を見失う¶
科目Bでは、配列の中身と添字を同時に追う必要があります。
例えば、
mid = 5
は値が5という意味ではありません。
「配列の5番目を見る」という意味です。
data[5] = 50
のように、添字と実際の値を分けて考えることが大切です。
科目Bではコードを暗記するより、動きを追えることが大切¶
二分探索のコードをそのまま暗記しても、科目Bで少し違う形の問題が出ると解けなくなることがあります。
大切なのは、
「中央を見る」 「比較する」 「不要な半分を捨てる」 「残った範囲でもう一度中央を見る」
という処理の意味を理解することです。
科目Bでは擬似言語を使い、処理の流れや変数の変化を追う力が求められます。
そのため、二分探索を勉強するときも、コードを眺めるだけではなく、left、right、midがどのように変化するのかを自分で追ってみてください。
二分探索を擬似言語で実行しながら学ぶならGiji Academy¶
擬似言語の難しいところは、参考書を読んでも「本当にこの動きで合っているのか」を確認しづらいことです。
Pythonで書き直して実行する方法もありますが、基本情報技術者試験の科目Bを勉強したいのであれば、最初から擬似言語のまま理解できた方が効率的です。
Giji Academyでは、擬似言語をブラウザ上で実行しながら学習できます。
二分探索についても、整列済みの配列から探索範囲を半分ずつ絞り込む処理を、擬似言語を使って学べる講座があります。
いきなり二分探索から始めるのが難しい場合は、
- 変数と代入
- 条件分岐
- 繰返し
- 配列
- トレース
- 線形探索
- 二分探索
という順番で進めることもできます。
「解説を読めば分かるけれど、自分で擬似言語を読むと分からなくなる」という方は、コードを実際に動かしながら確認してみてください。
登録不要で無料体験もできます。
Pythonで二分探索を書いてみる¶
基本情報技術者試験の科目B対策では擬似言語を優先したいですが、プログラミング自体も学んでいる方であれば、Pythonで実装してみるのも理解を深める方法の一つです。
def binary_search(data, value):
left = 0
right = len(data) - 1
while left <= right:
mid = (left + right) // 2
if data[mid] == value:
return mid
elif data[mid] < value:
left = mid + 1
else:
right = mid - 1
return -1
例えば、次のように実行します。
data = [10, 20, 30, 40, 50, 60, 70, 80, 90]
print(binary_search(data, 70))
Pythonでは配列の添字が0から始まるため、擬似言語の例と添字の考え方が異なる場合があります。
科目B対策として使う場合は、この違いで混乱しないようにしてください。
「試験対策」が目的なら擬似言語を中心に学び、Pythonはアルゴリズムそのものを深く理解したいときに試すくらいでよいと思います。
アルゴリズムをさらに勉強したい場合¶
二分探索以外にも、科目Bではデータ構造やアルゴリズムを読む力が必要になります。
二分探索を理解できたら、線形探索との違いを確認したあと、整列アルゴリズムやスタック、キューなどへ進んでいくと理解しやすいです。
アルゴリズムそのものを深く勉強したい場合は、以下のような書籍もあります。
![うかる！ 基本情報技術者 [午後・アルゴリズム編] 2021年版 福嶋先生の集中ゼミ (日本経済新聞出版)](https://m.media-amazon.com/images/I/51CLANtoLqL._SL500_.jpg)
こちらは旧試験制度の2021年版なので、現在の科目B対策用としてそのまま使うのではなく、アルゴリズムの考え方を補助的に学ぶ用途で利用してください。
また、元記事で紹介していた過去問題集も旧制度向けです。画像・リンクは残していますが、現在の試験対策では最新の科目A・科目Bに対応した教材を利用することをおすすめします。
まとめ¶
今回は、基本情報技術者試験の過去問を使って二分探索について解説しました。
問題の答えは、
ア：二分探索するデータ列は整列されている必要がある。
です。
二分探索で覚えておきたいポイントは、次のとおりです。
- 二分探索は整列済みのデータに対して利用する
- 先頭ではなく中央付近から確認する
- 比較するたびに探索範囲をおおよそ半分にする
- 計算量は
O(log n) - 擬似言語では
left、right、midの変化を追う
科目Bでは、アルゴリズム名を覚えるだけではなく、擬似言語になったときに「この処理で何が起きているのか」を追えることが大切です。
二分探索が分かったら、線形探索との違いを確認し、実際に擬似言語を動かしながらleft、right、midの値を追ってみてください。
Giji Academyでは、二分探索を含む探索アルゴリズムや、変数・繰返し・配列・トレースなどを、ブラウザ上で擬似言語を実行しながら段階的に学べます。
科目Bの擬似言語が苦手な方は、まず無料で実際に動かしてみてください。
Giji Academy｜擬似言語を実行しながら科目Bを学ぶ
あわせて読みたい
