Ищите элемент в векторе

Question

У меня есть вектор действительных значений, отсортированный по возрастанию.

Эти значения могут быть в диапазоне [0, 1]. Затем я выбираю значение x в этом диапазоне, и мне нужно найти, который является индексом меньшего значения, большего или равного x.

я могу решить эту проблему путем перебора всего массива:

vector<double> values; 
double x; 

for (auto val : values) 
{ 
    if (x <= values) 
    { 
     // found 
     break; 
    } 
} 

Есть ли более быстрый способ получить тот же результат? Я думал о бинарном поиске, но как его реализовать?

Answer 1

Использование std::lower_bound:

#include <iterator> 
#include <algorithm> 

std::distance(begin(values) 
      , std::lower_bound(begin(values), end(values), x)); 

Если элемент не существует, это даст вам индекс один больше, чем у последнего элемента.

DEMO

Answer 2

Вы знаете SO не сайт, который вы запрашиваете кто-то, чтобы написать вам код, так возьмите этот пример из std::binary_search и сделать свой путь:

// binary_search example 
#include <iostream>  // std::cout 
#include <algorithm> // std::binary_search, std::sort 
#include <vector>  // std::vector 

bool myfunction (int i,int j) { return (i<j); } 

int main() { 
    int myints[] = {1,2,3,4,5,4,3,2,1}; 
    std::vector<int> v(myints,myints+9);       // 1 2 3 4 5 4 3 2 1 

    // using default comparison: 
    std::sort (v.begin(), v.end()); 

    std::cout << "looking for a 3... "; 
    if (std::binary_search (v.begin(), v.end(), 3)) 
    std::cout << "found!\n"; else std::cout << "not found.\n"; 

    // using myfunction as comp: 
    std::sort (v.begin(), v.end(), myfunction); 

    std::cout << "looking for a 6... "; 
    if (std::binary_search (v.begin(), v.end(), 6, myfunction)) 
    std::cout << "found!\n"; else std::cout << "not found.\n"; 

    return 0; 
} 

Как сказал Петр, это не даст вам индекс , но ответ «да/нет». Однако, это должен быть самый простой подход, таким образом, самый быстрый.

Answer 3

Вы можете использовать operator[] для прямого доступа к элементам в векторе точно так же, как массив, вместо использования итератора для начала с начала. Я предполагаю, что вы уже знаете двоичный поиск. Реализовать его в массиве - это то, что вы можете найти где угодно, поэтому я не буду объяснять это вам здесь. Просто рассматривайте вектор как массив.

Answer 4

Функция lower_bound может удовлетворить ваши требования, и вы можете использовать его, как показано ниже:

iter =lower_bound(values.begin(),values.end(),x);