Usage examples of binary search

I just realized that in my 4+ years of Java programming (mostly desktop apps) I never used the binary search methods in the Arrays class for anything practical. Not even once. Some reasons I can think of:

1. 100% of the time you can get away with linear search, maps or something else that isn't binary search.
2. The incoming data is almost never sorted, and making it sorted requires an extra sorting step.

So I wonder if it's just me, or do a lo开发者_如何学运维t of people never use binary search? And what are some good, practical usage examples of binary search?

On the desktop, you're probably just dealing with the user's data, which might not be all that big. If you are querying over very large datasets, shared by many users, then it can be a different matter. A lot of people don't necessarily deal with binary search directly, but anyone using a database is probably using it implicitly. If you use AppEngine, for example, datastore queries almost certainly use binary search.

I would say it boils down to this:

If we are going to do a binary search, we're going to have a key to search by. If we have a key, we're probably using a map instead of an array.

There's another very important thing to keep in mind:

Binary search is a clear-cut example of how thinking like a good programmer is very different than thinking like a normal person. It's one of those cognitive leaps that makes you really think about taking operations that are traditionally done (when done by humans) in order-n time and taking it down to order-lg-n time. And that makes it very, very useful even if it's never used in production code.

I hardly ever, if ever use a binary search.

But I would if:

• I needed to search the same list multiple times
• the list was long enough to have a performance problem (although I'm often guilty of micro-optimization)

However, I often use hash tables / dictionaries for fast lookups.

For production code on my day job, a Set or Map is always good enough so far.

For algorithmic problems that a I solve for fun, binary search is a very useful technique. For starters, if the set of elements never changes (i.e. you are never going to insert or delete elements in the set being queried) a Map/Set has no advantage over binary search - and a binary search over a simple array avoids a lot of the overhead associated with querying a more complex data structure. In many cases I have seen it to be actually faster than a HashMap.

Binary search is also a more general technique than just querying for membership in a set. Binary search can be performed on any monotone function to find a value for which the function satisfies a certain criteria. You can find a more detailed explanation here. But as I said, my line of work does not bring up enough computationally involved problems for this to be applicable.

Assume you have to search an element in a list.

You could use linear search, you’ll get O(n).

Alternatively, you could sort it by fastest algorithm (O(log n)*n), and binary search(O(log n)). You’ll get O((log n)*n + log n).

That means when searching large size of list, binary search is better. Also, it depends data structure of list. If list is a link based list, binary search is bad practice.