Via Simon, Tim Bray has a great article On the Goodness of Binary Search.
There's a story I heard from a prof, that the basic Binary Search idea was around when Alan Turing was still in diapers, but that the first 18 published implementations were buggy. And I know for a fact that the first few times I coded it I got it wrong.
All that said, the core idea of binary search is mind-bogglingly simple; you have a sorted array, you look at the middle element which tells you what you're looking for is in the top or bottom half, then you take that half, rinse and repeat until done.
Monday, March 24, 2003
Permalink
Feel free to post a comment below. Please see my comment policy.
Formatting Rules (No HTML):