Binary search is an algorithm that finds an element in a sorted list.

To find an element in a list it is divided in the middle. If the mid element is the target it has been found. Should the mid element be bigger than the target element the search continues on the left side of the middle. If the mid element is smaller than the target element the search continues on the right side of the middle. Again the relevant side of the middle is divided in half and the procedure continues as above.

The algorithm

Here is an illustration of how binary search might work with an example list of 12 items and a target value of 7.

This is the sorted list of items that we search through looking 
for the element with the value of 7. 

–––––––––––––––––––––––––––––––––––––––––––––––––––––––
| 1 | 2 | 4 | 7 | 8 | 9 | 10 | 12 | 13 | 15 | 20 | 26 |
–––––––––––––––––––––––––––––––––––––––––––––––––––––––

The first step is to look at the value in the middle and see if it is 
the element with the value 7 we are looking for. 

The value in the middle is 

––––––
| 10 |
––––––

10 is not 7. Since 7 is smaller than 10 and this is a sorted list we can 
assume 7 can be found on the left of 10. Hence we discard the right 
and work with the list to the left of 10:

–––––––––––––––––––––––––
| 1 | 2 | 4 | 7 | 8 | 9 |
–––––––––––––––––––––––––

We now check again if the mid value is our target element. The mid value is

–––––
| 4 |
––––– 

and that again is not 7, so we have to keep looking. In this case 7 should be 
found to the right of 4. Therefore we can discard everything left of 4, 
including 4, since we already checked if it was the element we were 
looking for. We are left with:

–––––––––––––
| 7 | 8 | 9 |
–––––––––––––

This mid element is 8. Since that also isn't the target value we now look to the left of 8 and find one element, 7.

–––––
| 7 |
–––––

This remaining value matches our target value of 7. It has been found.

One of the advantages of binary search is that the size of the list could double from 12 to 24 and only 1 step is added for our search algorithm to perform. You can read more about binary search here: https://en.wikipedia.org/wiki/Binary_search_algorithm

Linear search, i.e. going through the list item by item until the target value has been found has one main advantage: It can be applied to unsorted lists. However it becomes very inefficient on long lists.

The repetition of the same procedure lends itself well to a recursive implementation, which was chosen in the example below.

Recursion means the function calls itself. Recursion is not necessary for binary search, but works well since the same set of steps are repeated until a base condition is met.

The implementation in C

bool search(int value, int values[], int n)
{
    return binary_search(value, values, 0, n);
}

bool binary_search(int value, int values[], int start_point, int end_point)
{
    do 
    {
      int mid_point = (start_point + end_point) / 2;

      if (start_point <= end_point) // check that the start_point is smaller than the end_point
      {
        if (value == values[mid_point])
        {
            return true;
        }
        else if (value < values[mid_point])
        {   
            // search left of mid_point
            return binary_search(value, values, 0, mid_point - 1);
        }
        else if (value > values[mid_point])
        {
            // search right of mid_point
            return binary_search(value, values, mid_point + 1, end_point);
        }
      }
      return false;
    }
    while (end_point > 0); // ensure the array has more than 0 elements
}

Binary search only works on sorted lists. The sort function below sorts a list using the bubble search algorithm. The sort() function takes an array and the length of the array. It then switches each element from left to right that is unsorted moving smaller elements to the left and bigger ones to the right. This is repeated until the entire array is sorted.

void sort(int values[], int n)
{
    int swap_counter = 0;

    do
    {
        swap_counter = 0;

        for (int i = 0; i < n; i++)
        {
            int pos1 = i;
            int pos2 = i+1;

            int values_pos1 = values[pos1];
            int values_pos2 = values[pos2];

            if (values[pos1] > values[pos2]) // switch the order of the two numbers
            {
                values[pos1] = values_pos2;
                values[pos2] = values_pos1;

                swap_counter++;
            }
            else if (values[pos1] < values[pos2]) // don't switch the order of two numbers
            {
                values[pos1] = values_pos1;
                values[pos2] = values_pos2;
                // return;
            }
        }
    }
    while (swap_counter > 0);
}

I wrote the sort and search functions as part of edX and HarvardX’ CS50x class’ problem sets. I highly recommend CS50 if you want to dig deeper. Sort and search algorithms are discussed at length in week 3.