二分探索法の使い道

二分探索法は、検索したい値が配列の中にあるか判定するだけでなく、「所与の条件を満たす最小値を求めよ」という最適化問題にも応用でき、さらには「N個すべての値をx以下にできるか判定せよ」という判定問題にも応用が効く、使いこなせるとカッコいいアルゴリズムの一つです。

配列から目的の値を探索する二分探索法

BinarySearch1.py

# 二分探索法
# 計算量：O(logN)
def binary_search(key, a):
    left = 0
    right = len(a)
    while right >= left:
        mid = left + (right-left)//2
        if a[mid] == key:
            return mid
        elif a[mid] > key:
            right = mid - 1
        elif a[mid] < key:
            left = mid + 1
    return -1

N = int(input())
a = list(map(int, input().split()))

binary_search(N, a)

# 入力
# 10
# 3 5 8 10 14 17 21 39

# 出力
# 3

条件を満たす最小値を求める二分探索法

BinarySearch2.py

# 最小値を返す二分探索法
# 配列aの中でa[i]≧keyという条件を満たす最小の添字iを返す
def binary_search2(key, a):
    left = 0
    right = len(a)
    while right >= left:
        mid = left + (right-left)//2
        if a[mid] == key:
            return mid
        elif a[mid] > key:
            right = mid - 1
        elif a[mid] < key:
            left = mid + 1
    return right+1

# ペア和問題
# N個の整数a0,...,aN-1と、　N個の整数b0,...,bN-1からから１個ずつ整数を選び、
# その和が整数K以上となる範囲での最小値を求める

# 入力受取
N, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# bに無限大を表す値を追加
b.append(99999)

# bを昇順にソート
b.sort()

# 暫定最小値を格納
min_ = 99999

# aを固定して解く
for i in range(N):
    iter_ = binary_search2(K-a[i], b)
    if min_ > a[i] + b[iter_]:
        min_ = a[i] + b[iter_]
print(min_)

最適化問題を判定問題に帰着して解く二分探索法

BinarySearch3.py

# AtCoder Beginner Contest 023 D - 射撃王
# N個の風船が初期値h[i]の高さにあり、秒速s[i]で上昇するとし、1秒に1つの速さで風船を
# 割っていき、風船が取り得る最大の高さの最小値を求める

# 入力受取
N = int(input())
h = list(map(int, input().split()))
s = list(map(int, input().split()))

# 二分探索法で解く
left, right = 0, 99999
while right - left > 1:
    mid = (left + right) // 2

    # mid以内で風船を割り切れる（風船が取り得る最大の高さの最小値）かの判定
    ok = True

    # 各風船を割るまでの制限時間t[i]を用意
    t = [0 for i in range(N)]

    # 初期値の高さと比較し、各風船の制限時間を格納
    for i in range(N):
        if mid < h[i]:
            ok = False
        else:
            t[i] = (mid - h[i]) // s[i]

    # 制限時間に余裕がない順にソートし、順に判定
    t.sort()
    for i in range(N):
        if t[i] < i:
            ok = False

    # 判定結果に基づき、midを更新  
    if ok:
        right = mid
    else:
        left = mid

print(right)