Where can I get a "useful" C++ binary search algorithm?

Question

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

A simple 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
    else
        return end; // not found
}

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

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

There is a set of them:

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

Search for:

• lower_bound
• upper_bound
• equal_range
• binary_search

On a separate note:

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

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

The shortest implementation, wondering why 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 https://en.cppreference.com/w/cpp/algorithm/lower_bound

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;
}

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

Check this function, qBinaryFind:

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

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

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

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

Example:

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 is included in the <QtAlgorithms> header which is a part of the Qt library.