Binary Search

The Algo as I can recall

So this quick discussion about Binary search is because one of the readers namely 'alifnoon' on my other blog wanted to see how many software engineers can actually write a correct binary search algorithm, which we all feel is quite simple. I agreed to do the exercise and post the results on this blog.

This code piece is something which I studied in Robert Sedgwick's book some years back,

public bool SearchItem(object itemToSearch, object[] itemList)
{
int leftIndex =1;
int rightIndex = itemList.Length;
int median=0;

while(rightIndex >= leftIndex)
{
median = (leftIndex + rightIndex) / 2;

if(itemToSearch == itemList[median])
return true;

if(itemToSearch < itemList[median])
rightIndex = median - 1;
else
leftIndex = median + 1;

}

return false;

}

I believe this is the code which follows divide and conquer approach. I stayed true to my words and gave you what I had in my mind.

My Two Cents
In the second part of this post, let me add a few things. I went ahead and searched around and came across this

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

where the writer has mentioned that there is a major flaw in binary search.

So alifnoon, I do want to give my two cents. I don't think that this is a flaw in the algo , it's more about scope definition. We can easily add the information to algo that it will work for values up to XYZ. It's understandable that they couldn't cover such scenarios mainly because they never really had to deal with such large values. If I look in this direction then right and left indexes are defined as int, and their values can become too large to beat an int.

If we would try to come up with applications which would work for every scenario and would have undefined scope then I doubt there is any chance of making one.

So just like any other field, algorithms are continuously evolving depending on changing requirements. That's how I feel :)

Conclusion
Thanks alifnoon for raising this issue, I sort of enjoyed this exercise and have decided to do some exercises out of programming pearls, it's almost an year that I last touched it.