値のちょうど小さい要素の位置のバイナリ検索

Question

C++初心者ここ！並べ替えられたベクトルv（一意でない値を持つ）とスカラーxがある場合、どのようにバイナリ検索を実行して、xと等しいか小さい要素の位置を返すことができます。

std::vector<double> v { 0.9,0.78,0.6,0.4,0.33,0.2,0.2,0.2,0.07 } 
double x = 0.7; 

int position = BinaryFindPosition(v.begin(),v.end(),x); 
// position is 2 

Answer 1

std::lower_boundを使用してください。あなたのベクトルが大ツー小さな注文されているので、あなたがrbegin()とrend()代わりのbegin()とend()を使用する必要があることに注意してください：

std::vector<double> v { 0.9, 0.78, 0.6, 0.4, 0.33, 0.2, 0.2, 0.2, 0.07 }; 
double x = 0.7; 
auto pos = std::distance(std::lower_bound(v.rbegin(), v.rend(), x), v.rend()); 
cout << pos << endl; 

Demo.