At which n does binary search become faster than linear search on a modern CPU?

Question

Due to the wonders of branch prediction, a binary search can be slower than a linear search through an array of integers. On a typical desktop processor, how big does that array have to get before it would be better to use a binary search? Assume the structure will be used for many lookups.

Answer 1

You might want to take a look at this article, which discusses the question you asked.

Answer 2

Not many - but hard to say exactly without benchmarking it.

Personally I'd tend to prefer the binary search, because in two years time, when someone else has quadrupled the size of your little array, you haven't lost much performance. Unless I knew very specifically that it's a bottleneck right now and I needed it to be as fast as possible, of course.

Having said that, remember that there are hash tables too; you could ask a similar question about them vs. binary search.

Answer 3

I've investigated this question in detail an have summarized my findings in this blog post.