アルゴリズム (線形探索・二分探索)

探索は「目的の値がどこにあるか」を見つける基本アルゴリズム。線形探索と二分探索の違いを理解しましょう。

日野 こむぎ

リストの中から特定の値を探すのって、どうやるのが普通?

藤森 さやか 先生

一番素朴なのは線形探索?
ね。
先頭から1個ずつ順番に比較していく方法なのよ。

青木 澪

計算量は最悪で O(n) ね。
データが大きいと遅いけれど、ソート不要だから配列がランダムでも使えるのが利点。
一方、ソート済みなら二分探索?
が圧倒的に高速よ。

桃井 すみれ

二分探索って、どんなふうに動くんですかぁ?

藤森 さやか 先生

辞書を引くようなイメージね。
真ん中を見て、目的の値より大きければ前半、小さければ後半に絞る。
これを繰り返していくのよ。

青木 澪

毎回半分に絞っていくから、計算量は O(log n) になるの。
1000個から探すのに約10回、100万個でも約20回で済むのよ。

日野 こむぎ

おぉ、すごっ!
でも、なんか前提条件とかあるんだよね?

青木 澪

そう、配列がソート済みであることが必須。
ソートのコストも考慮して使い分けるの。

桃井 すみれ

なるほどぉ〜、データの状態で使い分けるんですねぇ♪

二分探索を添字でトレースする

昇順配列 [3, 8, 12, 17, 23, 31, 42] から23を探します。試験では値だけでなく、探索範囲の左端・右端・中央の添字を書きながら追うと安全です。

1. 左端0、右端6なので中央は3。値17は23より小さいため、0〜3を捨てて左端を4にする。
2. 左端4、右端6なので中央は5。値31は23より大きいため、5〜6を捨てて右端を4にする。
3. 中央4の値が23なので発見。7要素を3回の比較で見つけられた。

見つからない場合は、更新を繰り返して左端が右端を超えた時点で探索終了です。中央を調べた後は、その位置も探索済みなので left = mid + 1 または right = mid - 1 と更新します。

日野 こむぎ

二分探索って速いなら、最初に毎回ソートすれば全部これでよくない?

青木 澪

一度だけ探すのに毎回 O(n log n) のソートをすると、線形探索 O(n) より総コストが大きくなることがあります。
既に整列済みか、同じデータを何度も検索するかで判断します。

桃井 すみれ

中央の値が違ったら、中央を次の範囲に残してもいいですかぁ?

藤森 さやか 先生

残すと同じ中央を選び続け、無限ループになる実装があるわ。
中央は比較済みなので必ず除外すること。
問題文の添字が0始まりか1始まりかも最初に確認しましょう。