テクノロジ系 / アルゴリズムとプログラミング
二分探索
二分探索は、整列済みデータの中央を調べ、探索範囲を半分ずつ狭めて目的の値を探す方法です。
もう少し詳しく
二分探索では、配列などが昇順または降順に整列されていることが前提です。中央の値と目的の値を比較し、目的の値が小さければ前半、大きければ後半だけを次の探索範囲にします。線形探索のように先頭から順番に確認する方法より効率がよく、データ件数が多いほど差が出ます。ただし、未整列データにはそのまま使えません。
試験での見方
例：1, 3, 5, 7, 9, 11, 13から9を探す場合、まず中央の7と比較し、9は7より大きいので後半の9, 11, 13に範囲を絞ります。
FEでは、比較回数や計算量O(log n)、探索範囲の更新、整列済みであることの確認が問われます。「半分ずつ減る」「中央を見る」という条件があれば二分探索を疑います。