二分探索

二分探索とは

ある条件Pを満たす集合と満たさない集合の境界値を求める問題で、その集合の境界面が一つしかないときに使える。（説明が下手）

なんかこう数直線でこっから右がokでこっから左がngってなっているみたいな、、、、

まず、全体を二つに分けて、するとそのどっちかはokかngだけの集合となっているので、それをmidにして、、、、なんかまとめる必要ないですね。自分ではわかっているのでリクエストがあれば頑張って言語化します。

実装

let mut ok = n as isize;
let mut ng = -1;

while ok - ng > 1 {
    let mid = (ok + ng) / 2;
    if a[mid as usize] >= k {
        ok = mid;
    } else {
        ng = mid;
    }
}

これはokの集合が右側にある時ですね！