[ACCEPTED]-Where can I get a "useful" C++ binary search algorithm?-binary-search

Accepted answer
Score: 105

There is no such functions, but you can 9 write a simple one using std::lower_bound, std::upper_bound or std::equal_range.

A simple 8 implementation could be

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
        return end; // not found

Another solution 7 would be to use a std::set, which guarantees the 6 ordering of the elements and provides a 5 method iterator find(T key) that returns an iterator to the 4 given item. However, your requirements might 3 not be compatible with the use of a set 2 (for example if you need to store the same 1 element multiple times).

Score: 10

You should have a look at std::equal_range. It will return 2 a pair of iterators to the range of all 1 results.

Score: 6

There is a set of them:


Search for:

On a separate 5 note:

They were probably thinking that searching 4 containers could term up more than one result. But 3 on the odd occasion where you just need 2 to test for existence an optimized version 1 would also be nice.

Score: 3

If std::lower_bound is too low-level for 4 your liking, you might want to check boost::container::flat_multiset. It 3 is a drop-in replacement for std::multiset 2 implemented as a sorted vector using binary 1 search.

Score: 3

The shortest implementation, wondering why 2 it's not included in the standard library:

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;

From 1 https://en.cppreference.com/w/cpp/algorithm/lower_bound

Score: 2
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;
        int mid=(start+end)/2;
            return mid;
        else if(var<array[mid]){
    return 0;

Example: Consider an array, A=[1,2,3,4,5,6,7,8,9] Suppose 8 you want to search the index of 3 Initially, start=0 7 and end=9-1=8 Now, since start<=end; mid=4; (array[mid] which 6 is 5) !=3 Now, 3 lies to the left of mid 5 as its smaller than 5. Therefore, we only 4 search the left part of the array Hence, now 3 start=0 and end=3; mid=2.Since array[mid]==3, hence 2 we got the number we were searching for. Hence, we 1 return its index which is equal to mid.

Score: 1

Check this function, qBinaryFind:

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

Performs a binary 11 search of the range [begin, end) and returns 10 the position of an occurrence of value. If 9 there are no occurrences of value, returns end.

The 8 items in the range [begin, end) must be 7 sorted in ascending order; see qSort().

If 6 there are many occurrences of the same 5 value, any one of them could be returned. Use 4 qLowerBound() or qUpperBound() if you 3 need finer control.


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)

The function 2 is included in the <QtAlgorithms> header which is a part 1 of the Qt library.

Score: 0

std::lower_bound() :)


Score: 0

A solution returning the position inside 3 the range could be like this, using only 2 operations on iterators (it should work 1 even if iterator does not arithmetic):

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-p)/2;  // overflow safe (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++;
            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;


More Related questions