問題 No.1933
二分探索アルゴリズムに関する記述として不適切なものはどれか。
【正解の解説】
探索対象のデータ列が予め昇順または降順に整列されている必要はない。
辞書で言葉を調べるとき、あいうえお順に並んでいるからこそ真ん中を開いて前か後ろかを判断できますよね。もし順番がバラバラなら、どこに目的のデータがあるか見当がつかないため、端から順番に探すしかなくなってしまいます。二分探索の最大のキモは『綺麗に並んでいること』なので、整列が不要というこの選択肢が不適切になります。
スポンサーリンク
【その他の選択肢の解説】
探索処理における計算量のオーダーは、要素数が倍増しても処理時間が変化しない。
要素数が倍増しても処理時間がまったく変化しないのはO(1)のハッシュ法などの特徴です。二分探索は要素数が倍になると、探す回数がちょうど1回増えるアルゴリズムです。階段を1段登るごとに倍の広さの部屋を半分こしていくイメージを持つと、データが増えると少しだけ手間が増える感覚が掴めるはずです。
探索範囲を毎回半分に絞り込んでいくため、ハッシュ法と比較してメモリ効率が非常に高い。
ハッシュ法はデータを高速に探すために、裏側で大きなハッシュテーブルという専用のメモリ領域をたくさん用意する必要があります。一方で二分探索は、いま手元にある配列のデータをそのまま使うため、追加の巨大なメモリをほとんど消費しません。この点は二分探索の大きな強みであり、この選択肢の指摘している内容は正しい事実となります。
探索対象のデータ構造として、動的な要素の追加や削除が容易な連結リストが適している。
二分探索は一瞬でデータの『真ん中』の要素を指定して見に行く必要があるため、インデックス番号で一発アクセスできる配列が得意です。しかし、電車が1列に繋がった連結リスト構造では、真ん中の要素を知るために先頭から順番に切符をめくって辿るしかありません。これでは二分探索の『一発で真ん中を見る』という最大のメリットが消えてしまうため、不向きなデータ構造です。