二分探索

読了目安 約3分

ソート済み配列を半分ずつ絞り込んで O(log N) で探す。めぐる式と答えの二分探索。

ソート済みの配列なら、前章の線形探索より速く探せます。 真ん中と比べれば、目当ての値がどちらの半分にあるか分かるからです。

候補を半分に絞る操作を繰り返す探し方が二分探索で、10 億個の候補も約 30 回で 1 個に絞れます。

めぐる式

二分探索は、境界の更新を 1 つ誤ると無限ループになりがちです。 そこで、めぐる式と呼ばれる定型を覚えます。 条件を 1 つ決め、2 つの位置に印を付けて管理します。

• ok：条件を満たすと確定した位置
• ng：条件を満たさないと確定した位置

例として、条件「値が x 以上」を満たす最初の位置を探します。 最初は、配列の外を仮の確定位置とみなして両端に置きます。 真ん中の mid を調べて ok か ng を動かし、印が隣り合ったら ok が答えです。

let a = [11, 13, 26, 26, 40, 52]
let x = 26

var ng = -1        // ここより左は「x 未満」で確定
var ok = a.count   // ここより右は「x 以上」で確定
while ok - ng > 1 {
    let mid = (ok + ng) / 2
    if a[mid] >= x {
        ok = mid
    } else {
        ng = mid
    }
    print("ng = \(ng), ok = \(ok)")
}
if ok < a.count {
    print("x 以上が最初に現れるのは a[\(ok)]")
} else {
    print("x 以上の値はありません")
}

ループの間ずっと保たれる性質を不変条件と呼びます。 めぐる式の不変条件は「ok は常に条件を満たし、ng は常に満たさない」です。 どちらか一方だけを動かすので、この関係は最後まで崩れません。

だから終了時の ok を、条件を満たす最小の位置だと言い切れます。

試してみよう: x を 100 に変えて、ok がどうなるか確かめてください。

答えで二分探索

探す場所は配列の中とは限りません。 「答えは x 以上か?」という判定が、x を大きくするとどこかで No に切り替わって戻らないとします。 この単調な判定さえ書ければ、答えそのものを絞り込めます。

長さ 8、14、20 の丸太から同じ長さの棒を 6 本切り出すとき、棒をどこまで長くできるでしょうか。 「長さ x で 6 本取れるか」は、x が短いほど成り立ちやすい単調な判定です。

let logs = [8, 14, 20]
let need = 6

func canCut(_ x: Int) -> Bool {
    var total = 0
    for len in logs {
        total += len / x
    }
    return total >= need
}

var ok = 1     // 長さ 1 なら必ず 6 本取れる
var ng = 21    // 最長の丸太より長いと 1 本も取れない
while ng - ok > 1 {
    let mid = (ok + ng) / 2
    if canCut(mid) {
        ok = mid
    } else {
        ng = mid
    }
}
print("最大の長さ: \(ok)")

ok が ng の左に来ましたが、不変条件は同じなので向きの覚え直しは不要です。

計算量

1 回の判定で候補が半分になるので、二分探索は O(log N) です。 答えで二分探索するときは、判定 1 回の計算量に log(答えの範囲) が掛かります。

学びどころ

演習

昇順にソート済みの配列 A と、Q 個の整数 x が与えられます。 各 x について、x 以上の値が最初に現れるインデックスを 0 始まりで出力してください。 x 以上の値が 1 つもなければ、A の要素数 N を出力してください。

入力は 1 行目に N、2 行目に A、3 行目に Q、続く Q 行に x です。

制約: 1 ≤ N ≤ 100000、1 ≤ Q ≤ 100000。

入力例:
5
1 3 3 5 9
4
3
4
0
10

出力例:
1
3
0
5

func lowerBound(_ a: [Int], _ x: Int) -> Int {
    var ng = -1
    var ok = a.count
    while ok - ng > 1 {
        let mid = (ok + ng) / 2
        if a[mid] >= x {
            ok = mid
        } else {
            ng = mid
        }
    }
    return ok
}

_ = readLine()
let a = readLine()!.split(separator: " ").map { Int($0)! }
let q = Int(readLine()!)!
for _ in 0..<q {
    let x = Int(readLine()!)!
    print(lowerBound(a, x))
}