# 二分探索をバグらせない用メモ ## 1. 以上、以下、未満、より大きい ```cpp int idx, x; ``` ### x以上最小の要素 ```cpp idx = lower_bound(a.begin(), a.end(), x) - a.begin(); if (idx >= a.size()) { // そのような要素は存在しない } ``` ### x以下最大の要素 ```cpp idx = upper_bound(a.begin(), a.end(), x) - a.begin() - 1; if (idx < 0) { // そのような要素は存在しない } ``` ### x未満最大の要素 ```cpp idx = lower_bound(a.begin(), a.end(), x) - a.begin() - 1; if (idx < 0) { // そのような要素は存在しない } ``` ### xより大きい最小の要素 ```cpp idx = upper_bound(a.begin(), a.end(), x) - a.begin(); if (idx >= a.size()) { // そのような要素は存在しない } ``` ## 2. 条件を満たす要素の個数 ```cpp int cnt; // 個数 ``` ### l <= A[i] <= rを満たすiの個数 ```cpp cnt = upper_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l); ``` ### l <= A[i] < rを満たすiの個数 ```cpp cnt = lower_bound(a.begin(), a.end(), r) - lower_bound(a.begin(), a.end(), l); ``` ### A[i] >= xを満たすiの個数 ```cpp cnt = a.end() - lower_bound(a.begin(), a.end(), x); ``` ### A[i] > xを満たすiの個数 ```cpp cnt = a.end() - upper_bound(a.begin(), a.end(), x); ``` ### A[i] <= xを満たすiの個数 ```cpp cnt = upper_bound(a.begin(), a.end(), x) - a.begin(); ``` ### A[i] < xを満たすiの個数 ```cpp cnt = lower_bound(a.begin(), a.end(), x) - a.begin(); ```