STLで二分探索

動機

二度と悲劇を繰り返さないために

悲劇

lower_boundとupper_bound

STLに含まれる両関数、文字通り上界と下界を与える。

• lower_bound
  • keyより真に大なる区間の下界
• upper_bound
  • keyより真に小なる区間の上界

例によって左閉半開区間だなと理解したけど、えびちゃんみたいな理解もあるみたい。これもわかる。

えびちゃんの解釈では、lower_bound(x) は x と等価な要素（a <= x かつ x <= a、C++ 的にはたぶん !(x < a) && !(a < x)）の下側の境界で、upper_bound(x) はその上側の境界だと思ってます
equal_range(x) でそのペアが返ってくるので、そんなような気持ちになりました

— えびちゃん (@rsk0315_h4x) August 15, 2019

signed main() {
  ios::sync_with_stdio(false);
  ll n = 10;
  vector<ll> a(n);
  REP(i, n)  a[i] = i;
  a[2] = 3;
  REP(i, n) cout << i << " ";cout << endl; # index
  REP(i, n) cout << a[i] << " ";cout << endl;
  auto lower = lower_bound(all(a), 3);
  auto upper = upper_bound(all(a), 3);
  cout << lower - a.begin() << endl;
  cout << upper - a.begin() << endl;
  return 0; 
}

/* output
0 1 2 3 4 5 6 7 8 9 
0 1 3 3 4 5 6 7 8 9 
2
4
*/