問題 No.3114
二分探索アルゴリズムの特徴や適用条件に関する記述として不適切なものはどれか。
【正解の解説】
探索対象のデータ列が予め昇順または降順に整列されている必要はない。
これは辞書を引くときに、ページがバラバラにめくられていたら意味がないのと同じです。二分探索は「データが綺麗に並んでいるからこそ、真ん中を見て半分を潔く捨てられる」という大前提があり、整列されていない場合は使えないため、この記述が不適切となります。
スポンサーリンク
【その他の選択肢の解説】
探索対象のデータ列の中央に位置する要素を確認して大小比較を行う処理を繰り返す。
初学者が「なんで半分になるの？」と疑問に思う部分ですが、1〜100の中から50を探すとき、まず50と比べて大きければ一瞬で前半の50個を捨てられる仕組みです。この動作を繰り返すことで爆発的にスピードが上がります。
探索範囲を毎回半分に狭めながら効率よく目的のデータを特定するため計算量が少ない。
計算量が非常に少ない（O(log n)）ため、数億件のデータからでも一瞬でお目当てを見つけ出せる超優秀なアルゴリズムです。効率よく範囲を狭めていくこのスピード感こそが二分探索の真骨頂です。
ポインタを先頭から順に一つずつ移動させながらすべての要素を網羅的に走査する。
先頭から一つずつしらみつぶしに探していく方法は、バラバラに散らかった部屋から物を探すようなものでデータ数に比例して時間がかかります。二分探索の賢い「真ん中を見て半分にする」動きと混同しないよう注意が必要です。