二分探索
ある条件を満たす最大もしくは最小の値を求めるための手法の1つ。一般に$ f(x) \lt kを満たす最大の$ xもしくは$ f(x) \gt kを満たす最小の$ xを求める場合に使う。応用範囲は広く、また計算量が$ \log(N)になるので重宝するが、前提として$ fが単調増加もしくは単調減少である必要がある。
区間を徐々に狭めていって、区間が十分に小さくなったら答えとする手法だが、実装上は、とくに整数を扱う場合は、片方を開区間、もう片方を閉区間として扱うと扱いやすくなる。
たとえば配列$ a_i がソートされているとして$ a_i \le k となる最大の$ i を求めたいとする。このとき、区間としては$ [l, r) を考え、この区間を徐々に狭める。区間の初期値は$ [0, n+1) (ただし$ n は$ a_i の要素数)とする。区間の縮め方は次のとおり。$ m = \lfloor\dfrac{l + r}{2}\rfloor として、もし$ a_{m} \le k なら、$ m は条件を満たすので$ l = m 、そうでないなら、条件を満たさないので$ r = m にすればよい。見てわかるように、常に区間$ [l, r) は条件を満たすように狭まるので、最終的に$ l + 1 = rになるまでこれを続ければ、求める答えは$ lになる。なお、すべての$ a_iが$ kより大きかった場合は、$ l = 0となることに注意。
逆に$ a_i \ge k となる最小の$ i を求めたい場合は、区間$ (l, r] を考えればよい。このとき範囲の狭めかたは、$ a_m \ge kなら$ r=m、そうでないなら$ l=mとして、最終的に$ rが得られる答えになる。すべての$ a_iが$ k未満の場合は、$ r = n + 1となる。
code:java
// Returns the largest index of the array where a_i <= k.
// If no element is smaller than or equal to k, returns -1.
public int upperBound(int[] a, int k) {
int left = -1;
int right = a.length;
while (right - left > 1) {
int mid = (left + right) / 2;
left = mid;
} else {
right = mid;
}
}
return left;
}
// Returns the smallest index of the array where k <= a_i.
// If no element is greater than or equal to k, returns a.length.
public int lowerBound(int[] a, int k) {
int left = -1;
int right = a.length;
while (right - left > 1) {
int mid = (left + right) / 2;
right = mid;
} else {
left = mid;
}
}
return right;
}