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.