Binary Search

Let's start with the standard search problem: say we are given a sorted sequence of positive integers and are required to find out if a number, N, exists in the sequence. There are several places where the search problem shows up naturally; for example, a receptionist looking for a customer's file in a set of files that are kept ordered by customer IDs or a teacher looking for the marks obtained by a student in their register of students. They are both, in effect, solving the search problem.

Now, we can approach the problem in two different ways. In the first approach, we iterate over the entire sequence, checking whether each element is equal to N. This is called a linear search and is shown in the following code:

bool linear_search(int N, std::vector<int>& sequence)

{

    for (auto i : sequence)

    {

        if (i == N)

          ...