Truly Understanding Binary Search

Implementing Binary Search

To implement binary search, we will start with a function
“binary_search”:

int binary_search(int a[], int n, int needle)
{
  // ...
}

It takes as input:

• a – an array containing the haystack (sorted in increasing order of values);
• n – the size of the haystack;
• needle – the element we are looking for

and it outputs:

• -1 – if the needle is not in the haystack, or
• i – a position between 0 (inclusively) and n (exclusively) in the
  haystack at which the needle occurs.

We start by initializing the two indices l and r as discussed above,
by the first and the last element in the array:

int binary_search(int a[], int n, int needle)
{
  int l = 0;
  int r = n - 1;
  // ...
}

Recall that the property that the segment [l, r] fulfils is that the
needle is definitely between l and r, if it occurs at all in the
haystack.

We now loop for as long as the segment of interest contains at least
an element and therefore there is a chance of finding the needle:

int binary_search(int a[], int n, int needle)
{
  int l = 0;
  int r = n - 1;
  while (l <= r) {
    // ...
  }
  // ...
}

We now have to compute the middle of the segment [l, r] (rounded down to the nearest integer):

int binary_search(int a[], int n, int needle)
{
  int l = 0;
  int r = n - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    // ...
  }
  // ...
}

We now check if the needle is exactly at position m:

int binary_search(int a[], int n, int needle)
{
  int l = 0;
  int r = n - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (a[m] == needle) {
      return m;
    }
    // ...
  }
  // ...
}

If not, then a[m] must be either strictly smaller or strictly larger
than the needle, in which cases we shorten the segment of interest accordingly:

int binary_search(int a[], int n, int needle)
{
  int l = 0;
  int r = n - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (a[m] == needle) {
      return m;
    } else if (a[m] < needle) {
      l = m + 1;
    } else { // a[m] > needle for sure
      r = m - 1;
    }
  }
  // ...
}

In the case where a[m] < needle, there is no chance to find
the needle to the left of m, as the elements to the left of m are even
smaller, and therefore we update l to m + 1.

In the last case, where a[m] > needle, there is no chance to find the
needle to the right of m, as the elements to the right of m are even
larger, and therefore we update r to m – 1.

Finally, if the segment of interest becomes empty without us having
found the needle, then surely the needle does not occur in the
haystack and therefore we return “-1”.

int binary_search(int a[], int n, int needle)
{
  int l = 0;
  int r = n - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (a[m] == needle) {
      return m;
    } else if (a[m] < needle) {
      l = m + 1;
    } else { // a[m] > needle for sure
      r = m - 1;
    }
  }
  return -1;
}

Check out the next page for caveats and possible variations of our implementation.

• 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