問題 No.1839
あらかじめ昇順や降順に並び替えられた複数のデータの中から、目的のデータが格納されている位置を特定するために、中央のデータと比較しながら探索範囲を半分に絞り込んでいくアルゴリズムはどれか。
【正解の解説】
二分探索（バイナリサーチ）
これは辞書で目的の単語を探すときの動きにそっくりです。分厚い辞書の真ん中を開いて「探したい言葉はこれより前か後ろか」を判断し、関係ない半分をバッサリ捨てていくことで、あっという間に目的のページにたどり着くことができます。データ数が数万件あっても数回〜十数回の比較で探し出せる圧倒的なスピードが魅力です。
スポンサーリンク
【その他の選択肢の解説】
線形探索（リニアサーチ）
線形探索はデータが並び替えられていなくても使える万能さがありますが、本棚の本を左から1冊ずつすべて確認していくようなものなので、データが増えるほど時間がかかります。「半分に絞り込む」という効率的なアプローチではなく、すべてのデータをしらみつぶしに確認する点が出題者の罠になりやすいので注意しましょう。
ハッシュ探索（ハッシュサーチ）
ハッシュ探索はデータの並び替えが不要で一瞬でデータを見つけ出せる強力な手法ですが、中央の値と比較して範囲を「半分に絞り込む」という仕組みではありません。辞書を引くのではなく、ロッカーの番号札を見て一発で荷物を取り出すようなイメージの技術であり、探索アルゴリズムの仕組みが根本的に異なります。
幅優先探索（ブレッドファースト）
迷路の攻略やSNSの友達の繋がりを調べる際によく使われるグラフ理論向けの探索手法であり、一本の直線上に綺麗に並んだ配列データを効率よく探す今回の問題文の状況とは適用するデータ構造が異なります。アルゴリズムの適用対象が混同しやすいため、問題文の「並び替えられた複数のデータ」というキーワードを見落とさないようにしましょう。