Debugging Binary Search - The Difficulty of Getting It Right


By Alex Allain
Recently, a friend of mine described a program he was working on as "pretty simple -- not real computer science". Having worked on numerous projects that were "pretty simple" until I tried to write and test the code, I was skeptical. Instead of arguing, I thought I'd give my friend a challenge.



I had just the right example: binary search. Seems simple enough, doesn't it? The basic algorithm for a binary search requires a sorted array for which random accesses are constant time (otherwise it doesn't make any sense not to perform a linear search). Given that the array is of size k, split the array in half -- test the middle element, originally k/2; if it's the value you're searching for, return the current index. Otherwise, if you have only one element in your subarray, return a sentinel indicating that you can't find the value. If that's not the case, if your search key is less than the middle element, perform the same operation on the elements from the start to k/2 - 1; if the middle element is less than your search key, perform the search on the subarray of k/2 + 1 to k. Every time you do this, you cut the size of the array to search in half -- so it takes O(log(k)) time, and about 10-15 lines of code. How many bugs can you possibly have?

Back to the story. I'll call my friend Joe to protect his pride. "Joe, let's make a bet. If you can write a perfect binary search function in the next hour -- and include a working main function for easy testing -- I'll buy you lunch tomorrow. Otherwise, you buy me lunch. The only stipulation is that you can't test your code. Of course, you can compile it to make sure there aren't any compiler bugs."

Joe: "I won't need to compile it. I'll send you my untested, uncompiled code by 12:30."

With that, we shook hands and I left him to work.

42 minutes later, I received his 50 line program, reproduced below (with a few minor modifications).
#include <iostream>

int bin_search(int* array, int size, int value)
{
        return bin_search(array, 0, size-1, value);
}

int bin_search(int* array, int start, int end, int value)
{
        if (start==end)
        {
                if (array[start]==value) return start;
                else return -1;
        }
        else if (start==end-1)
        {
                if (array[start]==value) return start;
                else if (array[end]==value) return end;
                else return -1;
        }
        // We know there is at least 1 element between start and end
        int midInd=(start+end)/2;
        int midVal=array[midInd];
        if (midVal==value) return midInd;
        else if (midVal>value) return bin_search(array,start,midVal-1,value);
        else return bin_search(array,midVal+1,end,value);
}

using namespace std;
int main()
{
        int size;
        cin>>size;
        int* array=new int[size];
        for (int i=0; i<size; i++)
        {
                cin>>array[i];
        }
        int value, result;
        cin>>value;
        result=bin_search(array,size,value);
        if (result==-1) cout<<"Sorry, not found\n";
        else cout<<"This is element #"<<result+1<<endl;
}
Before reading the rest of this article, look through the code and figure out whether or not it works; if it doesn't work, see how many bugs you can find.

Next: Who Won the Bet, and Why
Related articles

Learn more about search techniques

Learn more about the various sorting algorithms