【にぶんたんさく】
二分探索 とは？
最終更新:
💡 並びの規則を使って、探す範囲を半分ずつにする
並びの規則を使い、候補を半分ずつ絞る探索。ソート済み配列での手順、比較回数、境界、挿入位置と値の発見の違いを解説します。
📌 このページのポイント
ひよこ 二分探索は、真ん中を見る探し方？
ペンギン先生 そうだよ。昇順に並んだ配列なら、中央の値と探す値を比べる。探す値が中央より小さければ左、大きければ右の範囲へ進む。毎回、不要になった側を候補から外していくんだ。
ひよこ 並びがバラバラでも使える？
ペンギン先生 中央の値だけでは、どちらに目的の値があるか判断できないよ。配列で値を探す場合は、比較に使う規則でソートされていることが必要になる。ソートする費用もあるので、一回の探索だけで必ず得になるとは限らない。
ひよこ どれくらい少ない回数で探せるの？
ペンギン先生 中央へのアクセスや比較を一定の費用で行える配列なら、探索はO(log n)だよ。例えば候補の左右端を含め、中央との一回の比較で小さい・等しい・大きいを判定する実装では、1024件の最大回数は11回になる。
ひよこ Pythonのbisectは、見つかった場所を返す？
ペンギン先生 bisect_leftは、その値を入れて順序を保てる位置を返す。値が既にあるなら、その値が並ぶ範囲の手前だよ。本当に値があるかは、返された位置が配列内かを確認して、そこにある値と比べるんだ。
ひよこ 実装では、何に気を付けるの？
ペンギン先生 左右端を含むか、右端を含まないかなど、範囲の約束をそろえる。空の配列、最初と最後、存在しない値、重複も確認しよう。固定幅整数では中央を求める足し算が上限を超える場合もあるので、言語に合う計算方法を使うよ。
もっと詳しく知りたい人へ
1024件なら、log₂1024の10回ではない？
log₂1024は10ですが、実際の最大回数は実装と何を数えるかによります。本文の左右端を含む探索では、最後に一つ残った候補も調べるので最大11回です。nが1以上なら、この実装の最大の比較ステップ数は⌊log₂n⌋+1です。O(log n)は増え方を表し、正確な回数そのものではありません。
二分探索で挿入場所を探せば、追加もO(log n)？
配列やPythonのリストでは、場所を探した後に後続の要素をずらす費用がかかります。Pythonのinsortは探索がO(log n)でも、挿入部分のO(n)が支配します。また連結リストでは中央までたどる費用もあるため、比較回数と処理時間を分けて考えます。
まとめ：ざっくりこれだけ覚えればOK！
「二分探索」って出てきたら「並びの規則を使って、探す範囲を半分ずつ絞る方法」と思えばだいたいOK！
📖 おまけ：英語の意味
「Binary Search」 ＝ 二分探索
💬 binaryは二つに分けることを表します。昇順の配列なら、中央より小さい側か大きい側かを判断して、探索する範囲を減らしていきます。