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.
views:
677answers:
5
A:
You might want to take a look at this article, which discusses the question you asked.
zPesk
2009-08-14 02:17:40
That article assumes all operations take the same amount of time.
joeforker
2009-08-14 02:50:04
+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
2009-08-14 02:38:30
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
2009-08-14 14:24:03
+1
A:
I've investigated this question in detail an have summarized my findings in this blog post.
Mark Probst
2010-04-30 16:45:28