views:

677

answers:

5

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.

A: 

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

zPesk
That article assumes all operations take the same amount of time.
joeforker
+1  A: 

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.

Peter
The similar question already exists in SO.
joeforker
+3  A: 
Unknown
I think C is closer to 17.
joeforker
@joeforker, then binary search would be faster at 117 elements.
Unknown
Seems a shame to +1 as your rep was such a neat number (10,000)
Rich Seller
@ Rich Seller, I maxed out today. Just upvote me tomorrow when the rep counter resets at 12 AM GMT
Unknown
@Unknown the secret is that the branch in a linear search will be predicted correctly until the item is found.
joeforker
+3  A: 
Alex Martelli
You're compiling with-O3 right?
GMan
This is -O -- -O3 makes linear search a bit worse, 178 msec or so, and binary search a bit better, 222 msec or so.
Alex Martelli
+1  A: 

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

Mark Probst
Great article, Mark.
joeforker