Debugging Binary Search – The Difficulty of Getting It Right

[ Debugging Binary Search – The Difficulty of Getting It Right ]

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.

Advertisements

Author: iotmaker

I am interested in IoT, robot, figures & leadership. Also, I have spent almost every day of the past 15 years making robots or electronic inventions or computer programs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s