二分探索は「境界」を探す

答えがソート順に並ぶ、または判定が False→True と一度だけ変化するなら、調べる範囲を半分ずつ狭められます。

言語：Python / 計算量：O(log 範囲 × 判定コスト)

前提：累積和で区間を引き算にする

考え方

1. 単調性を先に確認します。
2. lo は不成立、hi は成立という不変条件を保ちます。
3. hi-lo=1 まで繰り返すと hi が最初の成立位置です。

具体例

x²≥20 になる最小非負整数は5。4²は16で不足、5²は25で成立します。

実装

k = 20
lo, hi = -1, k + 1
while hi - lo > 1:
    mid = (lo + hi) // 2
    if mid * mid >= k:
        hi = mid
    else:
        lo = mid
print(hi)

注意する条件

真偽が True,False,True のように戻る条件には使えません。初期境界の成立も証明します。

確認問題

x²≥30 の最小非負整数 x は？

実装課題

整数 K (0 ≤ K ≤ 10^18) に対し x²≥K を満たす最小非負整数 x を整数演算で求める。

入力:
30
出力:
6

k = int(input())
lo, hi = -1, k + 1
while hi - lo > 1:
    mid = (lo + hi) // 2
    if mid * mid >= k:
        hi = mid
    else:
        lo = mid
print(hi)

実戦につなげる補講

一度に全て読まなくて大丈夫です。今日は1節と1問から。

最初は「答え」ではなく境界を定義する

昇順の列でx以上になる最初の位置を探します。左にはx未満、右にはx以上、という境界です。該当がないときはNを返すと決めます。ソートされていなければ、この左右の性質がなく二分探索できません。

Pythonではbisectの返す意味を説明する

bisect_left(a,x)はx以上の先頭、bisect_right(a,x)はxより大きい先頭の位置です。値そのものではありません。[2,5,5,9]でx=5なら左は1、右は3。差の2が5の個数になります。

二分探索の外側も数える

判定がO(N)の「答えを二分探索」なら、二分探索全体はO(N log V)です。探索区間が半分になるからといって、判定の仕事が消えるわけではありません。単調性の説明と判定コストの見積もりを両方行います。

記憶の仕方を変えると境界が現れる

値ごとに出現位置の列を作ると、その列は元の添字順に追加するだけで昇順になります。ある区間内の出現回数は2つの境界位置の差。全ての値について長さNの累積表を持たずに済みます。

段階式の追加演習

1. 重複と端の確認

a=[2,5,5,9]で、bisect_left(a,5)、bisect_right(a,5)、bisect_left(a,10)は？

2. 実装：範囲内の値の数

昇順のaについてlo以上hi以下の個数を返すcount_betweenを書いて。lo<=hiとする。

from bisect import bisect_left, bisect_right
def count_between(a, lo, hi):
    return bisect_right(a, hi) - bisect_left(a, lo)

3. なぜ二分探索できない？

a=[1,8,3,10]で「5以上か」を調べながら二分探索してよい？

4. 判定関数の料金

N=200000個のデータを読む判定を、約30回行う。主要な走査回数は？

公式過去問への橋渡し

ABC248 D / 公式解説

値ごとの出現位置を保存し、区間の境界を二分探索する。前処理と質問処理を分けて数える。

ABC143 D / 公式解説PDF

3要素の全探索から、2要素を固定して残りの候補数を境界で求める発想へ進む。

見本を閉じて確認

• 何を繰り返しているかを説明できる
• 使える条件と使えない条件を1つずつ言える
• 見本を閉じて実装し、小さい入力で確かめられる

読了の記録・下書き・メモへ