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

Posted by joeforker on Stack Overflow See other posts from Stack Overflow or by joeforker
Published on 2009-08-14T01:57:06Z Indexed on 2010/04/30 16:47 UTC
Read the original article Hit count: 135

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.

© Stack Overflow or respective owner

Related posts about premature-optimization

Related posts about search