Zhaopeng's Homepage

My tech notebook

Binary search algorithm illustration

Posted on In

“A picture is worth a thousand words”

In order to explain to a friend how Binary search algorithm works, I drew several pictures to show solution of a simple problem using this algorithm. Here I would like to share it in this post.

As shown in the figure below, we are given a sorted array v = [1, 2, 3, 4, 5, 7, 9, 10, 12, 17], and we want to find index of the target number 9. One can see easily that the answer should be 6 (suppose index of the first element is 0).

Alt Text

Binary search algorithm illustration

In Binary search algorithm, we define three pointers to elements: l, r and mid. They point respectively to the lower (left) bound index, the upper (right) bound index and the middle index of the range for searching. We calculate mid as mid = l + (r-l)/2.

Initially, we search the entire array. So l = 0, r = 9 and mid = 4. Here is the first step:

Alt Text

The element pointed by mid is 5 and it is smaller than our target number 9. So we narrow down the searching range to the right half of the array: l = mid+1 = 5, r = 9 and mid is updated 7:

Alt Text

Now the element pointed by mid is 10 and it is larger than our target number 9. So we narrow down again the searching range to its left half.

Alt Text

We repeat the same steps until the element pointed by mid is equal to the target number 9. See, we find out the index of number 9 in this array is 6.
Alt Text

Binary search algorithm code

Below is the c++ code for this algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
* Binary search 
*/
int binSearch(vector<int>& array, int target) {

    int l = 0, r = array.size()-1;
    while (l<=r)
    {
        int mid = l + (r-l)/2;
        if(array[mid] == target)
        {
            return mid;
        }
        if(array[mid] > target)
        {
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }

    return -1;
   
}

Overview

I put all the steps of this example in one figure to demonstrate overview of the Binary search algorithm:

image

A similar problem

Here is a similar problem which can also be solved by varying a little the Binary search algorithm: in a sorted array with repeated elements, we would like to find index of the first occurrence of the target number. One can think of the solution. I will present the solution using figures in my next post.

Alt Text