sortとlower_bound
Pythonの sorted と bisect_left に対応する標準機能があります。返ってくるのが添字ではなくイテレータである点が違います。
言語：C++ / 計算量：例の処理による
前提：if・for・関数を書き換える / 二分探索は「境界」を探す
考え方
- sort(a.begin(),a.end()) で昇順。
- lower_bound は x 以上の最初の位置。
- it-a.begin() で添字に変換します。
具体例
[1,3,3,8] に対して lower_bound(3) の添字は1、upper_bound(3) は3です。
実装
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){vector<int>a={8,3,1,3};sort(a.begin(),a.end());cout<<lower_bound(a.begin(),a.end(),3)-a.begin()<<"\n";}注意する条件
lower_bound の前にソート（または条件に沿う分割）が必要です。end() を指す結果を参照してはいけません。
確認問題
[1,3,3,8] の upper_bound(3) の添字は？
解答と理由
3
3より大きい最初の値8が添字3です。
実装課題
N X とソート済み配列 A。X 未満の要素数を求める。N≤200000、値はint範囲。
入力:
4 3
1 3 3 8
出力:
1参考実装
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){int n,x;cin>>n>>x;vector<int>a(n);for(auto&v:a)cin>>v;cout<<lower_bound(a.begin(),a.end(),x)-a.begin()<<"\n";}