#c #search #vector #binary-search-tree
#c #Поиск #вектор #binary-search-tree
Вопрос:
Новичок в 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
Комментарии:
1. Просто — используйте
std::lower_boundилиstd::upper_bound.2. OP — Посмотрите, какие две функции, на которые вас ссылал @PaulMcKenzie. Поскольку вы сказали, что неуникальные значения, вы можете захотеть использовать
upper_bound. Также обратите внимание, что ваши значения сортируются в обратном порядке (сначала наибольшее значение). Вы должны использовать перегрузку, которая принимает компаратор.3. @HappyGreenKidNaps Вы можете использовать
rbegin()/rend()вместо пользовательского компаратора.
Ответ №1:
Используйте std::lower_bound . Обратите внимание, что, поскольку ваш вектор упорядочен от большого к малому, вы должны использовать rbegin() and rend() вместо begin() and 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;