テクノロジ系 / アルゴリズムとプログラミング
探索アルゴリズム
たくさんのデータの中から、目的のデータを見つけ出すための手順のことです。
意味を丁寧に確認
代表的なものに、先頭から順に1つずつ調べていく「線形探索（逐次探索）」と、あらかじめ並べ替えておいたデータの真ん中と比べて範囲を半分ずつ絞り込む「二分探索」があります。二分探索は調べる回数が一気に減るためデータ量が多いほど高速ですが、データが昇順や降順に整列済みであることが前提となる点に注意が必要です。目的に応じて適切な探索方法を選ぶことが効率化につながります。
覚え方
試験での見方
黒猫の辛口メモ
iパスでは「線形探索と二分探索の違い」「二分探索には事前のソート（整列）が必要」という知識がよく問われます。データが多いとき二分探索のほうが速い、という比較も頻出です。
1〜100の数字を当てるとき、毎回「真ん中の数より大きい？」と聞いて範囲を半分にしていくのが二分探索の考え方です。
二分探索＝「半分ずつ絞る」ので整列必須、線形探索＝「端から総当たり」なので整列不要、と対で覚えると混同しません。