бинарный поиск на с ++ со сравнением

Question

бинарный поиск на с ++ со сравнением

Я хотел бы выполнить бинарный поиск на C ++, по отсортированному вектору V.
В частности, я не заинтересован в поиске точного значения записи вектора. Я хотел бы найти позицию j записи, которая удовлетворяет V [j-1] <= X < V [j], где X — входные значения.

например:
для вектора v = {1, 4, 7, 12, 17, 55} и X = 8 функция должна возвращать 3.

Могу ли я использовать функцию STD binary_search со сложностью O (log (2))?

И как?

Большое спасибо,

Al.

1

binary-search c++

Решение

Другие решения

Стандартными функциями для этого являются upper_bound и lower_bound. Читать эти

http://www.cplusplus.com/reference/algorithm/upper_bound/
http://www.cplusplus.com/reference/algorithm/lower_bound/

Если вы прокрутите эти страницы немного вниз, вы найдете примеры, которые должны прояснить ситуацию 🙂

8

Примечание о функциях Bartosz связано:

upper_bound(begin, end, value) возвращает первый элемент больше чем данное значение. Это конец (или один за другим) интервала, в который он может быть вставлен и сохранить порядок
lower_bound(begin, end, value) вернуть первый элемент не менее чем данное значение. Это начало интервала, в который он может быть вставлен

Итак, на практике:

std::vector<int> v = {1, 4, 7, 12, 17, 55};
int x = 8;
auto first = std::lower_bound(v.begin(), v.end(), x);
auto last = std::upper_bound(first, v.end(), x);

должен дать first == last && *first == 12, Это потому, что полуоткрытый интервал [first,last) где x может быть вставлено пусто.

Обратите внимание, что это, как правило, более полезно, чем вы просили, потому что

std::vector::insert(iterator, value)

вставки до данный итератор, так что вы всегда можете использовать результат upper_bound Вот.

4

Источник

Accepted Answer

Согласно вашему требованию, правильная функция STL — это upper_bound. Синтаксис:

upper_bound(V.begin(),V.end(),val)-V.begin()

Вернет индекс на основе 0, который вы ищете.

2