読者です 読者をやめる 読者になる 読者になる

C++競プロ学習日記(仮)

( 学習記録であり解説Blogではないです )

Search - Binary Search |アルゴリズムとデータ構造|AOJ

アルゴリズムとデータ構造の本に沿った問題の
探索 2 | アルゴリズムとデータ構造 | Aizu Online Judgeを解きました。

#include <bits/stdc++.h>
using namespace std;
//二分探索
int main(){
    int N;
    cin >> N;
    vector<int> vc(N);
    for( auto&& x : vc ){
        cin >> x;    
    }
    sort(vc.begin(),vc.end());
    int M;
    cin >> M;
    vector<int> vc2(M);
    int count{};
    for( auto&& x : vc2 ){
        cin >> x;
        int left{},right = N, mid{};
        while( left < right ){            
            mid = ( left + right ) / 2;
            if( x == vc[mid] ){
                count++;
                break;
            }
            if( x > vc[mid] ){
                left = mid + 1;
            }else if( x < vc[mid] ){
                right = mid;
            }
        }
    }
    cout << count << endl;
    return 0;
}

二分探索vectorで書きました。
※本のサンプルコードとは異なります

二分探索は探索処理が大変イメージしやすく、コードとしても分かり易かったです。

参考:二分探索 | アルゴリズムとデータ構造 | Aizu Online Judge
参考動画:二分探索 - YouTube