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