Algorithms - Binary Search

 

Overview

Binary search algorithms  operate on various types of containers such as sequence, associative and unordered that are sorted to perform actions such as finding upper, lower, equal bounds for a value or its existence. 

These function accepts parameters like 

• iterators such as forward
• predicates such as  binary 
• Unary values.

The parameter type  Compare is a function that accepts two inputs and returns bool value (true or false).

 For example, bool issame(int i, int j) {return i == j;} or [](int i, int j) {return i == j;}

Details

Name	Description
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& val) ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& val, Compare comp)	Returns an iterator pointing to the first element in the sorted range [first,last] which returns false by the comparison function when compared with val as described below. The elements are compared using operator< function. The elements are compared using comp function.
Examples: vector<int> v{1,2,3,5}; //first //itr = begin(v)+2 auto itr = lower_bound (begin(v), end(v),3); //itr = begin(v)+3 itr = lower_bound (begin(v), end(v),4); //itr = end(v) itr = lower_bound (begin(v), end(v),6); //second //itr = begin(v)+2 itr = lower_bound (begin(v), end(v),3, less<int>()); //itr = begin(v)+3 itr = lower_bound (begin(v), end(v),4, less<int>()); //itr = end(v) itr = lower_bound (begin(v), end(v),6, less<int>());
ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,  const T& val) ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,  const T& val, Compare comp)	Returns an iterator pointing to the first element in the range [first,last] which returns false by the comparison function when compared with val as described below. The elements are compared using operator< function. The elements are compared using comp function.
Examples: vector<int> v{1,2,3,5}; //first //itr = begin(v)+2 auto itr = upper_bound (begin(v), end(v),2); //itr = begin(v)+3 itr = upper_bound (begin(v), end(v),4); //itr = end(v) itr = upper_bound (begin(v), end(v),6); //second //itr = begin(v)+2 itr = upper_bound (begin(v), end(v),2, less<int>()); //itr = begin(v)+3 itr = upper_bound (begin(v), end(v),4, less<int>()); //itr = end(v) itr = upper_bound (begin(v), end(v),6, less<int>());
pair<ForwardIterator,ForwardIterator> equal_range ( ForwardIterator first, ForwardIterator last, const T& val) pair<ForwardIterator,ForwardIterator> equal_range ( ForwardIterator first, ForwardIterator last, const T& val, Compare comp)	Returns the bounds of the subrange that includes all the elements of the sorted range [first,last] with values equivalent to val as described below. The elements are compared using operator< function. The elements are compared using comp function.
Examples: vector<int> v{1,2,3,3,5}; //first //p = {begin(v)+1,begin(v)+2} auto p = equal_range (begin(v), end(v),2); //p = {begin(v)+4,begin(v)+4} p = equal_range(begin(v), end(v),4); //p = {end(v),end(v)} p = equal_range (begin(v), end(v),6); //second //p = {begin(v)+1,begin(v)+2} p = equal_range (begin(v), end(v),2, less<int>()); //p = {begin(v)+4,begin(v)+4} p = equal_range (begin(v), end(v),4, less<int>()); //p = {end(v),end(v)} p = equal_range (begin(v), end(v),6, less<int>());
bool binary_search ( ForwardIterator first, ForwardIterator last,   const T& val) bool binary_search ( ForwardIterator first, ForwardIterator last,  const T& val, Compare comp)	Test if val exists in sorted sequence. Returns true if any element in the range [first,last] is equivalent to val, and false otherwise as described below. The elements are compared using operator< function. The elements are compared using comp function.
Examples: vector<int> v{1,2,3,5}; //first //b = true auto b = binary_search (begin(v), end(v),2); //b = false b = binary_search (begin(v), end(v),4); //b = false b = binary_search (begin(v), end(v),6); //second //b = true b = binary_search (begin(v), end(v),2, less<int>()); //b = false b = binary_search (begin(v), end(v),4, less<int>()); //b = false b = binary_search (begin(v), end(v),6, less<int>());

The example depicts the usage.

Summary of Examples

Name	Description	github	wandbox
Example	Usage	source    output	source + output