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

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
    else
        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).

You should have a look at std::equal_range. It will return 2 a pair of iterators to the range of all 1 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 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.

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.

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

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 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.

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.

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

std::lower_bound() :)

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

}