リリース・改善中
Algorithm
探索はデータから目的の値や位置を見つけるアルゴリズムです。線形探索、二分探索、lower_bound・upper_bound、答えの二分探索、ハッシュによる検索を扱います。
探索とは、データの集まりから目的の値を見つけたり、ある条件が初めて成り立つ位置を求めたりすることです。線形探索は要素を一つずつ比べるのでどんなデータにも使えます。二分探索はソート済みの範囲を毎回半分に絞り込むため、100万個の要素でも約20回の比較で答えが出ます。完全一致のキーを調べるだけなら、ハッシュテーブルが平均して定数時間で答えます。
ほとんどのプログラムは何かを調べるので、探索は最も基本的なアルゴリズムです。データベースのインデックス、入力補完、ログ解析、ルーティングテーブルはどれも探索に支えられています。また、二分探索は配列だけのものではありません。はい/いいえの条件が範囲の中で一度だけ切り替わるなら、答えそのものを二分探索できます。これにより、コーディング面接の多くの最適化問題が短く確実なコードになります。
まず線形探索と閉区間の二分探索を自分で書き、次に半開区間の lower_bound・upper_bound の形を、境界の扱いが自然に感じられるまで練習するとよいでしょう。小さな配列で動きを手で追い、自作のコードを Python の bisect モジュールとランダムな入力で比べて確かめ、最後に最適化問題で答えの二分探索と三分探索に取り組みます。
要素を一つずつ比べ、O(n) 時間かかります。ソートが不要で、要素が少ないときは最も速い選択になることも多いです。
ソート済みの範囲を毎回半分にし、O(log n) 時間で値を見つけます。ループで実装すれば追加メモリは O(1) です。
値以上、または値より大きい最初の位置を返します。両者の差が重複の個数になり、Python の bisect モジュールが両方を提供しています。
パラメトリックサーチは「実現できる最小の値は何か」をはい/いいえの判定に置き換え、答えの取りうる範囲を二分探索します。
lower_bound は半開区間 [lo, hi) を使い、値が x 以上になる最初のインデックスを返します。中央の値が x より小さければ左半分を、そうでなければ右半分を捨てます。contains はそのインデックスで値の有無を確かめ、最後の行は結果が標準ライブラリの bisect.bisect_left と一致することを確認します。
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.pyインストールから 探索 の中心となる考え方まで、6 章で順を追って学びます。
探索 について質問し、経験を共有し、意見を交わす場所です。
まだディスカッションはありません。最初の話題を始めましょう。
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。