Где взять «полезный» алгоритм двоичного поиска C ++?

Question

Мне нужен алгоритм двоичного поиска, который совместим с контейнерами C ++ STL, что-то вроде std::binary_search в заголовке <algorithm> стандартной библиотеки, но мне нужно, чтобы он возвращал итератор, указывающий на результат, а не простое логическое значение говорит мне, если элемент существует.

(Кстати, о чем, черт возьми, думал стандартный комитет, когда определяли API для binary_search?!)

Моя главная проблема заключается в том, что мне нужна скорость бинарного поиска, поэтому, хотя я могу найти данные с помощью других алгоритмов, как упомянуто ниже, я хочу воспользоваться тем, что мои данные отсортированы, чтобы получить преимущества бинарного поиска, а не линейного поиска.

пока lower_bound и upper_bound завершатся неудачно, если данные отсутствуют:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

Примечание: Я также в порядке, используя алгоритм, который не принадлежит пространству имен std, если он совместим с контейнерами. Как, скажем, boost::binary_search.

Answer 1

Нет таких функций, но вы можете написать простую, используя std::lower_bound, std::upper_bound или std::equal_range.

Простая реализация может быть

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Другим решением будет использование std::set, которое гарантирует упорядочение элементов и предоставляет метод iterator find(T key), который возвращает итератор для данного элемента. Однако ваши требования могут быть несовместимы с использованием набора (например, если вам нужно хранить один и тот же элемент несколько раз).

Answer 2

Вы должны взглянуть на std::equal_range. Он вернет пару итераторов в диапазон всех результатов.

Answer 3

Существует множество из них:

http://www.sgi.com/tech/stl/table_of_contents.html

Поиск:

• lower_bound
• upper_bound
• equal_range
• binary_search

На отдельной заметке:

Они, вероятно, думали, что поиск контейнеров может дать более одного результата. Но в странном случае, когда вам просто нужно проверить существование, оптимизированная версия тоже подойдет.

Answer 4

Если std :: lower_bound слишком низкоуровневый, вам может потребоваться проверить boost :: container :: flat_multiset . Это заменитель std :: multiset, реализованный в виде отсортированного вектора с использованием бинарного поиска.

Answer 5

Проверьте эту функцию, qBinaryFind :

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

Выполняет двоичный поиск диапазона [начало, конец) и возвращает позицию появления значения. Если там нет вхождений значения, возвращает конец.

Элементы в диапазоне [начало, конец) должны быть отсортированы в порядке возрастания; увидеть QSort ().

Если есть много случаев то же значение, любой из них может быть вернулся. Используйте qLowerBound () или qUpperBound (), если вам нужно лучше управление.

Пример:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

Функция включена в заголовок <QtAlgorithms>, который является частью библиотеки Qt .

Answer 6

std :: lower_bound ():)

Answer 7

Самая короткая реализация, интересно, почему она не включена в стандартную библиотеку:

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

С https://en.cppreference.com/w/cpp/algorithm/lower_bound

Answer 8

int BinarySearch(vector<int> array,int var)
{ 
    //array should be sorted in ascending order in this case  
    int start=0;
    int end=array.size()-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(array[mid]==var){
            return mid;
        }
        else if(var<array[mid]){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return 0;
}

Пример: рассмотрим массив, A = [1,2,3,4,5,6,7,8,9] Предположим, вы хотите найти индекс 3 Первоначально start = 0 и end = 9-1 = 8 Теперь, так как начало <= конец; середина = 4; (массив [mid] который равен 5)! = 3 Теперь, 3 лежит слева от середины как его меньше 5. Поэтому мы ищем только левую часть массива Следовательно, теперь start = 0 и end = 3; mid = 2. С массивом [mid] == 3, следовательно, мы получили номер, который искали. Следовательно, мы возвращаем его индекс, который равен середине. </p>

Answer 9

Решение, возвращающее позицию внутри диапазона, может быть таким, используя только операции над итераторами (оно должно работать, даже если итератор не арифметический):

template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{       
    const InputIterator beginIt = first;
    InputIterator element = first;
    size_t p = 0;
    size_t shift = 0;
    while((first <= last)) 
    {
        p = std::distance(beginIt, first);
        size_t u = std::distance(beginIt, last);
        size_t m = (p+u)/2;
        std::advance(element, m - shift);
        shift = m;
        if(*element == val) 
            return m; // value found at position  m
        if(val > *element)
            first = element++;
        else
            last  = element--;

    }
    // if you are here the value is not present in the list, 
    // however if there are the value should be at position u
    // (here p==u)
    return p;

}