二分探索
中央値の二分探索
中央値を小さい方から数えて ⌈n/2⌉番目とする
基準となる値を決めることで全ての配列の値をmidを超えるな超えないかの1,-1で表すことができる
その総和が1以上のとき中央値は基準となる値を超えることが言える
これを使えば中央値がX以上かという判定問題をO(N)で解け、二分探索に応用できる
平均値での二分探索
これも中央値と同じように基準となる値との差の総和と考える
平均値がXを超えるかという判定をO(N)でできる
並列二分探索
同じ条件での二分探索が複数個ある場合、同一の値を使った判定を解いていくことで高速化できる
クエリの数をQ,答えの最大値をM,判定にかかる時間をO(1),毎回の初期化にかかる時間をNとするならO(Qlog(M+N))で終わらせることができる