Cacher is the code snippet organizer for pro developers

• 二分探索 (O(logN))

//  v < b の個数
  std::lower_bound(v.begin(), v.end(), b) - v.begin();
//  v <= b の個数
  std::upper_bound(v.begin(), v.end(), b) - v.begin();
//  a <= v の個数
  v.end() - std::lower_bound(v.begin(), v.end(), a);
//  a < v の個数
  v.end() - std::upper_bound(v.begin(), v.end(), key);

- 二分探索（関数が複雑な時)
```c++
bool check(int x) {
  // process something
  // return true / false;
}

int main() {
  ...
  int ok = xxx, ng = xxx;
  while (abs(ok - ng) > 1) {
    int mid = (ok+ng)/2;
    if (check(mid)) ok = mid;
    else            ng = mid;
  }
  cout << ok << endl;
}

三分探索

double f(int x) {
  ......
  return hogehoge
}

int main() {
  int low=0, high=1e9;
  while(high - low < 1e-5) {
    int c1 = (low*2+high)/3;
    int c2 = (low+high*2)/3;
    if(f(c1) > f(c2)) low = c1;
    else              high = c2;     
  }
  cout << f(low) << endl;
}