※いろんな方が二分探索について解説してくださってるので今更まとめる必要もないと思いますが書きます
二分探索について
内容
ソートされた配列(同一の要素はないものとする)の中から任意の要素を対数時間($O(\log_2 N)$Nは要素数)で探し出すアルゴリズムです
例(数当てゲーム)
あなたはA君の思い描いている数を当てるゲームをします
A君の思い描いている数は1以上16未満です
できるだけ少ない回数の質問でA君の思い描(ryを当ててください
一つずつ数を言って行ってもいいですがこの方法だとA君の(ryが15の時、15回の質問が必要になります
もっと効率的な方法はないのでしょうか？
これは二分探索法を使って当てることができます
手順
まず変数l,rを
$l = 1,
r = 16$
と定義します
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| l | r |
次に変数midを
$mid = (r + l) ÷ 2$
と定義します
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| l | mid | r |
ここでA君に「数はmid(=8)未満ですか？」と質問、
ここでは便宜上yesと返ってきたことにします
rを
$r = mid$
と更新します
(noと返ってきた場合は
$l = mid$
とします)
そしてまた
$mid = (l + r) ÷ 2$
とします
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| l | mid | r |
ここでまたA君に「数はmid(=4)未満ですか？」と質問します
ここでは便宜上noと返ってきたことにします
$l = mid$
とし、
$mid = (l + r) ÷ 2$
とします
| 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| l | mid | r |
(以下これの繰り返し)
変数lとrの幅が寄って行っているのがわかると思います
最終的には
$r = l + 1$
となり、この時のlがA君の思い(ryです
(この手順の途中で常に、lはA君の思(ryとしてあり得る最小値、rはA君(ryとしてあり得ない最小値をとっています)
これが二分探索法の例です
コード
以下、二分探索のC++コードを載せておきます
template <typename T>
bool binary_search(vector<T> V, T x){ //Vの中からxを探し出す、返り値：xがVの中に存在するかどうか(存在する：true、存在しない：false)
int l = 0, r = (int)V.size();
while (r - l > 1) {
int mid = (r + l) / 2;
if (x < V[mid])
r = mid;
else
l = mid;
}
return V[l] == x;
}
上記のことをそのままコードにしただけなので解説は省きます
二分法について
内容
関数$f(x)$が
$f(a) < 0$
$f(b) > 0$
を満たす時に、反復計算で$f(x) = 0$となるxを求めるアルゴリズムです
例(比例の関数)
$f(x) = 0$ となるxを求めます(相対誤差$10^{-3}$以下で正解とします)
$f(x) = x (-4 ≤ x ≤ 5) $ と定義します
ここで二分探索の時と同じく$l = -4, r = 5$として反復計算していきます
・１回目
$
mid = (l + r) / 2 = 0.5
$
$
f(mid) = 0.5 > 0
$
$
r = mid = 0.5
$
・２回目
$
mid = (r + l) / 2 = -1.75
$
$
f(mid) = -1.75 < 0
$
$
l = mid = -1.75
$
・３回目
$
mid = (r + l) / 2 = -0.625
$
$
f(mid) = -0.625 < 0
$
$
l = mid = -0.625
$
・４回目
$
mid = (r + l) / 2 = -0.0625
$
$
f(mid) = -0.0625 < 0
$
$
l = mid = -0.0625
$
・５回目
$
mid = (r + l) / 2 = 0.21875
$
$
f(mid) = 0.21875 > 0
$
$
r = mid = 0.21875
$
・６回目
$
mid = (r + l) / 2 = 0.078125
$
$
f(mid) = 0.078125 > 0
$
$
r = mid = 0.078125
$
・７回目
$
mid = (r + l) / 2 = 0.015625
$
$
f(mid) = 0.015625 > 0
$
$
r = mid = 0.015625
$
(以下
$r - l ≤ 10^{-3}$
となるまで繰り返し)
流石に手計算は疲れるので最後までできませんでした
応用例
平方根
注)これは二分探索法ではなくて二分法です
平方根の求め方
rとlの相対誤差を設定して、誤差がそれ以下になるまで二分探索のような感じで求めればいいです
(ここでは誤差を$10^{-15}$に設定しています)
double square_root(double num){
double l = 0, r = num;
while (r - l > 1e-15) {
double mid = (r + l) / 2;
if (mid * mid > num)
r = mid;
else
l = mid;
}
return l;
}
平方根を応用して
mid * mid > num
の部分を変えるとn乗根も求められます
double n_root(double num, double n) {
double l = 0, r = num;
while (r - l > 1e-15) {
double mid = (r + l) / 2;
if (pow(mid, n) > num)
r = mid;
else
l = mid;
}
return l;
}
答えで二分探索
競プロの問題ではしばしば二分探索が使える時があります(というか頻出)
例題(Yokan Party)
問題文
左右の長さが
$L$ [cm] のようかんがあります。
$N$ 個の切れ目が付けられており、左から
$i$ 番目の切れ目は左から
$A_i$ [cm] の位置にあります。あなたは
$N$ 個の切れ目のうち
$K$ 個を選び、ようかんを
$K+1$ 個のピースに分割したいです。そこで、以下の値を スコア とします。・$K+1$ 個のピースのうち、最も短いものの長さ（cm 単位）
スコアが最大となるように分割する場合に得られるスコアを求めてください。
解法
答えとしてありうる最小値は0、最大値はLです
そのため、$l = 0, r = L$ として二分探索すれば良いです
二分探索にかかるのが$O(log L)$(logの底は2)
答えとしてその数値があり得るのか判定するのに
$O(N)$かかるので
全体計算量
$O(N log L)$で解くことができます
コード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll INF=1LL<<60;
#define rep(i,n) for(int i=0; i<((int)(n)); i++)
#define reps(i,n) for(int i=1; i<=((int)(n)); i++)
#define rrep(i,n) for(int i=((int)(n)); i>0; i--)
#define rreps(i,n) for(int i=((int)(n)-1); i>=0; i--)
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
void Main();
int main(){
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(15);
Main();
return 0;
}
//-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
bool f(vector<ll>& A, ll N, ll L, ll K, ll num) { //判定,O(N)まで
bool ans = false;
ll count = 0;
ll len = 0;
rep(i, N)
if (A[i] - len >= num) { //長さnumの切れ端ができるか
count++;
len = A[i];
}
if (L - len >= num) //最後の切れ端
count++;
if (count > K) //K + 1個の切れ端が作れるか
ans = true;
return ans;
}
void Main(){
ll N,L;
cin >> N >> L;
ll K;
cin >> K;
vector<ll> A(N);
rep(i, N) cin >> A[i];
//二分探索
ll l = 1, r = L + 1;//l:下限, r:上限
while (r - l > 1) {
//二分探索の判定
ll mid = (l + r) / 2;//真ん中の数
if (f(A, N, L, K, mid)) //OK
l = mid;
else //ダメ
r = mid;
}
cout << l << endl;
}
まとめ
競プロで頻出の二分探索と二分法について自分なりにまとめてみました
色々と応用が効くので覚えておいて損はないアルゴリズムだと思います
C++のSTLにはbinary_searchとかlower_bound、upper_boundが用意されているので自分で実装する必要はありませんが仕組みだけでも理解しておくべきだと思います