Lower&Upper Bound¶
The C++ standard library contains the following functions that are based on binary search and work in logarithmic time.

lower_bound: returns a pointer to the first array element whose value is at least $x$.

upper_bound: returns a pointer to the first array element whose value is larger than $x$.

equal_range: returns both above pointers
The functions assume that the array is sorted.
If there is no such element, the pointer points to the element after the last array element.
For example, the following code finds out whether an array contains an element with vlaue $x$.
1 2 3 4 

Then, the following code counts th enumber o f elements whose value is $x$
1 2 3 

Using equal_range
, the code becomes shorter:
1 2 

Finding the smallest solution¶
An important use for binary search is to find the position where the value of a function change.
Suppose that we wish to find the smallest vlaue $k$ that is a valid solution for a problem.
We are given a function
ok(x)
that returnstrue
if $x$ is valid solution and false otherwise.In addition, we know that
ok(x)
isfalse
when $x < k$ andtrue
when $x \geq k$.Now, the value of $k$ can be found using binary search.
1 2 3 4 5 

The search finds the largest value of $x$ for which
ok(x)
isfalse
.Thus, the next value
k = x + 1
is the smallest possible value for whichok(k)
istrue
.The initial jump length $z$ has to be lar enough, for exmaple some vlaue for which we know beforehand that
ok(z)
istrue
.The algorithm calls the function
ok
$\Omicron(lgz)$ times, so the total time complexity depends on the functionok
.For example, if the function works in works in $\Omicron(n)$ time, the total time complexity is $Omicron(nlgz)$.
Finding the maximum value¶
Binary search can also be used to find the maximum value for a function that is first increasing and then decreasing. Our task is to find a poisition $k$ such that
 $f(x) < f(x + 1 )$ when $x < k $, and
 $f(x) > f(x + 1)$ when $ x \geq k$
The idea is to use binary search for finding the largest value of $x$ for which $f(x) < f(x + 1)$.
This implies that $ k = x + 1$ because $f(x+1) > f(x + 2).
1 2 3 4 5 

Note that unlike in the ordinary binary search, here it is not allowed that consecutive values of the function are equal.
In this case it would not be possible to know how to continue the search.