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

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

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

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

найти:

• lower_bound
• объектом upper_bound
• equal_range
• binary_search

на отдельной Примечание:

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

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

std:: lower_bound ():)

проверить эту функцию, 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 библиотека.

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

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;

}

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 Первоначально, начало=0 и конец=9-1=8 Теперь, начиная с start

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

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