Truly Understanding Binary Search

How it Works – Overview

The trick in binary search is to exclude at each step large parts of the array where the needle cannot possible be found.

At each step, we will use two indices, l and r, such that

 _ _ _ _ ? ? ? ? ? ? ` ` ` ` `
         ^         ^
         l         r

everything to the left of l is smaller than the needle and everything to the right of r is larger than the needle.

Therefore, the needle can only be in the segment between l and r, if it occurs at all in the haystack. For this reason, we call the segment between l and r the segment of interest.

Binary search shrinks the segment of interest at each step by roughly a half of its size. Therefore, after not too many steps, we either hit the needle, and in this case we have found its position in the haystack, or the segment of interest becomes empty, in which case the needle does not occur in the haystack.

Initially, l points to the first element in the haystack and r points to the last element:

 * * * * * * * * * *
 ^                 ^
 l                 r

At each step, we take a look at the value that sits right in the middle of the segment of interest.

  middle of segment
         m
         v 
 * * * * * * * * * *
 ^                 ^
 l                 r

We compute the position of the middle as m = (l + r) / 2 or m = l + (r – l) / 2. If the division is not exact because there are an even number of elements between l and r, we round m to the nearest integer, down or up, doesn’t matter which way (usually down).

There are now three cases to consider, depending on the value found at position m in the haystack:

• In the first case, we get lucky and the needle is exactly at position “m”;
• If a[m] is smaller than the needle, every element before position m is even smaller. Therefore we reduce the segment of interest to [m + 1, r] instead of the current [l, r].

m and earlier positions contain values too small to be the needle
 vvvvvvvvv
 _ _ _ _ _ * * * * *
 ^                 ^
 l                 r
           ^^^^^^^^^
         new segment of interest

• If a[m] is larger than the needle, because our array is sorted in increasing order of values, everything after m position m is even larger. This means that we can reduce the segment of interest to [l, m – 1], instead of the current [l, r].

         m and subsequent positions contain values too large to be the needle
         vvvvvvvvvvv 
 * * * * ` ` ` ` ` `
 ^                 ^
 l                 r
 ^^^^^^^
 new segment of interest

At each step, the length of the segment of interest is roughly cut in half. Therefore, at some point, we either get lucky and hit the needle, or we end up with an empty segment of interest. In this last case, the needle does not occur in the haystack.

Check out the next page to see a running example.

• 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