二分探索 バイナリサーチ

  • 簡単でかつ効果が高いのでよく使うサーチ.
  • 意外と境界条件でバグりがち.味噌は,右側を配列の外において置く.
#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;
}