二分探索 バイナリサーチ
- 簡単でかつ効果が高いのでよく使うサーチ.
- 意外と境界条件でバグりがち.味噌は,右側を配列の外において置く.
#include<iostream> #include<vector> using namespace std; int main() { int d, n; cin >> d; cin >> n; vector<int> v(n); for (int i=0; i<n; ++i) cin>>v[i]; int l=0, r=v.size(), m=(l+r)>>1; while (l<r) { if (d == v[m]) { cout << "find: " << m << "\n"; return 1; } else if (d < v[m]) r=m; else l=m+1; m=(l+r)>>1; } cout << "not found\n"; return 0; }