線形探索は要素を順に確認し、二分探索は整列順を利用して探索範囲を半分ずつ絞ります。配列での最悪時間計算量は、それぞれO(n)とO(log n)です。ただし、二分探索の前提と前処理も確認しましょう。
条件と計算量の比較
| 比較 | 線形探索 | 二分探索 |
|---|---|---|
| 探し方 | 要素を順番に確認 | 中央と比較し残りの範囲を絞る |
| データの条件 | 整列不要 | 探索に使うキーで整列済み |
| 最悪の探索時間 | O(n) | 中央へ直接アクセスできる配列ではO(log n) |
| 最良の探索時間 | 先頭で見つかればO(1) | 最初の中央で見つかればO(1) |
線形探索：見つからない場合も考える
［18, 7, 25, 12］で12を探すなら、18→7→25→12の順に調べ、4番目で見つかります。存在しない30を探す場合も、基本的には最後まで確認します。未整列のデータを一度だけ調べたい場合などに使いやすい方法です。
二分探索：整列した範囲を半分ずつ絞る
昇順の［10, 20, 30, 40, 50, 60, 70］で50を探します。中央40より大きいので右の［50, 60, 70］へ、中央60より小さいので［50］へ絞り、発見します。中央値の選び方は要素数が偶数の場合などに規則が必要です。
見つからなければ範囲が空になった時点で終了します。同じ値が複数あっても探索できますが、通常の一致判定だけでは最初・最後の位置や全件が得られるとは限りません。必要な条件に合わせて探索を調整します。
100万件なら何回？
各要素との比較を1回と数える通常の二分探索では、100万件の配列は最悪でも約20回の中央要素の確認で範囲を絞れます。一方、線形探索では最大100万要素を確認します。この比較は整列済み配列の探索部分に限り、ソート時間や比較そのものの費用は別です。
二分探索が常に有利とは限らない
未整列のデータを1回だけ探すためにソートすると、その前処理の費用が必要です。何度も探索するのか、追加・更新が多いのかも考えます。また連結リストでは中央まで移動する手間があるため、比較回数O(log n)でも全体の処理時間まで同じとは限りません。
計算量の表し方は、O記法の記事で整理しています。
確認問題
未整列の配列を1回だけ検索するとき、二分探索の探索部分がO(log n)だから必ず線形探索より速い、と言えますか？
解答・解説を見る
言えません。二分探索には整列という前提があり、ソートなどの前処理も含めて考える必要があります。
探索と計算量をnoteでまとめて復習
無料noteには線形探索・二分探索の例と、O(n)・O(log n)の説明があります。探し方から計算量の増え方まで、つなげて復習できます。
ほかの教材は資格・目的別のnote教材ナビから選べます。
コメント