線形探索は順に調べる方法、二分探索は整列したデータの探索範囲を半分ずつ絞る方法です。比較回数だけでなく、整列の有無やデータ構造の前提も確認しましょう。
線形探索：先頭から順に確認
配列［2, 5, 8, 12, 16, 23, 38］から23を探す場合、左から2→5→8→12→16→23と比較します。この例では6回で見つかります。整列していないデータにも使えますが、見つからない場合などは全件を調べます。
二分探索：中央との比較で範囲を絞る
同じ昇順配列なら、中央の12と23を比較します。23の方が大きいので右半分［16, 23, 38］へ進み、その中央23で見つかります。この例では2回の比較です。目的の値が小さければ左半分を探します。
| 観点 | 線形探索 | 二分探索 |
|---|---|---|
| 整列 | 不要 | 比較規則に沿った整列が必要 |
| 最悪時の比較回数の増え方 | O(n) | O(log n) |
| 探索範囲 | 一つずつ確認 | おおむね半分ずつ絞る |
| 注意 | 大量データでは比較が増える | 整列や中央へのアクセスの費用を別に考える |
二分探索はいつでも高速とは限らない
配列など、中央の要素へ効率よくアクセスできる構造で、すでに整列済みなら二分探索が有効です。一度だけ探すために未整列データを整列する場合、整列の時間も含めて比較する必要があります。連結リストでは中央へ移動する費用もあるため、比較回数のO(log n)だけで実行時間を判断しないでください。
O表記は実際の秒数ではない
O(n)やO(log n)は、データ数nを増やしたときの計算量の増え方を表します。小さいデータでは定数部分や実装の違いも影響します。二分探索で範囲を半分ずつにすることと、対数の増え方を結び付けて覚えましょう。
確認問題
昇順配列［2, 5, 8, 12, 16, 23, 38］で二分探索を行い、最初に中央の12と比較しました。5を探す場合、次に調べる範囲はどちらでしょうか？
解答・解説を見る
左側の［2, 5, 8］です。5は中央の12より小さいので右側を除外できます。昇順に整列していることが、この判断の前提です。
計算量の増え方をまとめて学ぶ
無料noteではO(1)・O(log n)・O(n²)などの計算量を解説しています。探索方法の違いを理解したら、ほかのアルゴリズムと比較して復習できます。
ほかの分野は、資格・目的別のnote教材ナビから選べます。
コメント