More Techniques for Finding Things - Binary Search Trade-offs
(Page 3 of 5 )
Binary search has some very large advantages. First of all, its performance is O(log2 N) . People often don’t really grasp how powerful this is. On a 32-bit computer, the biggest log2 you’ll ever encounter is 32 (similarly, 64 on a 64-bit computer), and any algorithm that competes in an upper bound of a few dozen steps will be “good enough” for many real-world scenarios.
Second, the binary-search code is short and simple. Code that is short and simple is beautiful, for a bunch of reasons. Maybe the most important is that it’s easier to understand, and understanding code is harder than writing it. There are fewer places for bugs to hide. Also, compact code plays better with instruction sets, I-caches, and JIT compilers, and thus tends to run faster.
Third, once you’ve got that sorted array, you don’t need any more index structures; binary search is very space-efficient.
The big downside to binary search is that the data has to be kept in order in memory. There are some data sets for which this is impossible, but fewer than you might think. If you think you have too much data to fit in memory, check the price of RAM these days and make sure. Any search strategy that requires going to disk is going to be immensely more complex, and in many scenarios slower.
Suppose you need to update the data set; you might think that would rule out binary search because you have to update a huge, contiguous array in memory. But that turns out to be easier than you might think. In fact, your program’s memory is scattered randomly all over the computer’s physical RAM, with the operating system’s paging software making it look sequential; you can do the same kind of trick with your own data.
Some might argue that since a hash table isO(1), that has to be better than binary search’sO(log2N). In practice, the difference may not be that significant; set up an experiment sometime and do some measurements. Also, consider that hash tables, with the necessary collision-resolution code, are considerably more complex to implement.
I don’t want to be dogmatic, but in recent years, I’ve started to take the following approach to search problems:
- Try to solve it using your language’s built-in hash tables.
- Then try to solve it with binary search.
- Only then should you reluctantly start to consider other more complex options.
Next: Escaping the Loop >>
More Practices Articles
More By O'Reilly Media
|
 This article is excerpted from chapter four of Beautiful Code: Leading Programmers Explain How They Think, written by Andy Oram and Greg Wilson (O'Reilly, 2007; ISBN: 0596510047). Check it out today at your favorite bookstore. Buy this book now.
|
|
