Truly Understanding Binary Search

Example 1

Here is how binary search works on our running example.

haystack = 1 3 4 5 7 8 9
needle = 7

We start with l pointing to the leftmost element and r pointing to the rightmost element in the array.

haystack = 1 3 4 5 7 8 9
           ^           ^
           l           r
needle = 6

Let’s forget for a second about the actual contents of the haystack.

haystack = * * * * * * *
           ^           ^
           l           r
needle = 7

We compare the element in the middle of the segment of interest, which is 5, against the needle.

                 v
haystack = * * * 5 * * *
           ^           ^
           l           r
needle = 7

It is smaller than the needle, and therefore we restrict the segment of interest to the half on the right-hand side.

haystack = * * * 5 * * *
                   ^   ^
                   l   r
needle = 6

We compare the element in the middle of the new segment of interest, which is 8, against the needle.

haystack = * * * 5 * 8 *
           ^           ^
           l           r
needle = 7

It is larger, and therefore we restrict the segment of interest to the half on the left-hand side.

                     v
haystack = * * * 5 * 8 *
                   ^ 
                  l=r
needle = 7

We now compare the single element that remains in the segment of interest against the needle.

                   v
haystack = * * * 5 7 8 *
                   ^ 
                  l=r
needle = 7

They match and therefore we have found the needle and its position.

Note that we have only accessed 3 out of 7 elements in the
input array, and this hints at the reason why binary search is so
fast (check out page 5 for a more detailed explanation of the time complexity).

Check out the next page for an example where the needle does not occur in the haystack.

• Page 1 – Introduction
• Page 2 – How It Works – Overview
• Page 3 – Example 1
• Page 4 – Example 2
• Page 5 – Why Binary Search is so Fast
• Page 6 – Implementation
• Page 7 – Conclusion