二分探索をしよう！

線形探索はなのに対して二分探索はで済む！
そんな便利な二分探索をできるようにしよう！

目次

• 二分探索とは
• 実装方法
  • 使用例1: 飛び飛びの値から一致するものを探す
    • 方針
    • 実装例
  • 使用例2: 連続的な整数の集合から条件を満たす値を探す
    • 例題：平方根の整数部分
    • 問題文
      • 制約
      • 入力
      • 出力
      • 入力例1
      • 出力例1
      • 入力例2
      • 出力例2
    • 解答例

二分探索とは

二分探索とは、リストを半分ずつに区切って目標を探す探索法。
具体的には

1. 配列をソートする
2. 探索する区間の真ん中に点を打つ。
3. その点の値が目標の値より小さければ区間の後側を、大きければ前側を次の区間として再び②へ。
4. 求める値と一致していれば終了。

といったところ。
配列がソートされている必要があることに注意！

二倍に増えるごとにループの回数は１回分増えるってことで、最悪計算量は

実装方法

使用例1: 飛び飛びの値から一致するものを探す

方針

例として、この配列vecから入力inputと一致する値のインデックスを二分探索で調べてみよう。

int input = 19;
vector<int> vec = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int ans = -1;

ansは求める値を入れる変数。一つも一致しなかった場合-1のままになる予定。

この配列は既にソートされているから、まずは2.探索する区間の真ん中に点を打つことから始めよう。
区間はループの度に変わるから、扱いやすいように左端と右端をおいておく。

int left = 0;
int right = vec.size() - 1;

この区間に真ん中の点を打とう。その点をとしても良いのだが、 でオーバーフローが起こる恐れがあるので、ここでは としておこう。これならオーバーフローの心配はなく、元の式とも同値。

int mid = left + (right - left) / 2;

真ん中の点の位置を決めたから、この点の値を判定していく。

求める値と一致するなら通過、求める値より小さければ左端をmidより右側に、大きければ右端midより左側に移す。

if(vec[mid] == input) {
    ans = mid;
}
else if(vec[mid] < input){
    left = mid + 1;
}
else if(vec[mid] > input) {
    right = mid - 1;
}

第二・第三if節内では、第一ifよりinputと一致しないから+1, -1して範囲を片側に絞り込んでいる。

一致しなかった場合はループしてほしいのでwhileでmidの部分から囲む。
rightとleftが一致し、かつinputと一致しないときleftが+1するかrightが-1するので必ずleftはrightよりも右側に来る。
この状態になったら求める値が配列にないことがわかるから、ここでループを終了する。
よってコードは以下の通り。

int input = 19;
vector<int> vec = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int ans = -1;
int left = 0;
int right = vec.size() - 1;
while(left <= right) {
    int mid = left + (right - left) / 2;
    
    if(vec[mid] == input) {
        ans = mid;
        break; //ここでbreakがないと無限ループになるので注意
    }
    else if(vec[mid] < input){
        left = mid + 1;
    }
    else if(vec[mid] > input) {
        right = mid - 1;
    }
}

cout << ans << endl; //7

複数の値をチェックするため、扱いやすく関数にしよう。

実装例

#include <iostream>
#include <vector>
using namespace std;

int binary_search(vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        
        if(arr[mid] == target) {
            return mid;
        }
        else if(arr[mid] < target){
            left = mid + 1;
        }
        else if(arr[mid] > target) {
            right = mid - 1;
        }
    }
    return -1;
}

vector<int> vec = {2, 3, 5, 7, 11, 13, 17, 19, 23};

int main() {
    cout << binary_search(vec, 7) << endl; //3
    cout << binary_search(vec, 13) << endl; //5
    cout << binary_search(vec, 23) << endl; //8
    cout << binary_search(vec, 1) << endl; //-1
    cout << binary_search(vec, 20) << endl; //-1
    cout << binary_search(vec, 40) << endl; //-1
    return 0;
}

使用例2: 連続的な整数の集合から条件を満たす値を探す

簡単な例題を考える。

例題：平方根の整数部分

問題文

正の整数 が与えられます。 を満たす最大の整数 を求めてください。

制約

• 入力はすべて整数

入力

入力は以下の標準入力から与えられます。

N

出力

条件を満たす最大の整数 を出力してください。

入力例1

26

出力例1

5

入力例2

1000000000000000000

出力例2

1000000000

これを二分探索で求めよう。
という条件に対し、Xの値を考えると

• が小さいとき は成り立つ。
• がある値を超えて大きくなると、それ以降は は成り立たない。

ことがわかる。
これらを元に探索の区間を狭めていき、その条件の転換点である、ある値を見つければよい。
尚、先ほどの例で配列のインデックスとして使った整数が、今回はそのまま求める値となるので配列は必要ない。

前の例と同じく範囲を１点まで狭めていき、leftとrightの位置が逆転したときの最大の整数を出力してもよいが、今回はほんの少し別のアプローチで求める。
leftは常に条件を満たす値、rightは常に条件を満たさない値として考え、leftとrightが綺麗に隣あったとき(Nを挟む、またはleftとNが一致するとき)のleft、すなわちを求める。

midの判定の条件は であるが、 でオーバーフローが起こる恐れがあるので、 とする。

解答例

#include <iostream>
using namespace std;

int main() {
    long long N;
    cin >> N;

    long long left = 1;
    long long right = 1000000001LL; // 10^9 + 1

    //隣あったら終わり
    while (right - left > 1) {
        long long mid = left + (right - left) / 2;

        if (mid <= N / mid) {
            left = mid;
        } else {
            right = mid;
        }
    }

    cout << left << endl;

    return 0;
}