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: 133

Filed under:

premature-optimization

|

search

|

algorithm

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

Am I understanding premature optimization correctly?

as seen on Stack Overflow - Search for 'Stack Overflow'
I've been struggling with an application I'm writing and I think I'm beginning to see that my problem is premature optimization. The perfectionist side of me wants to make everything optimal and perfect the first time through, but I'm finding this is complicating the design quite a bit. Instead of… >>> More
Premature-Optimization and Performance Anxiety

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
While writing my post analyzing the new .NET 4 ConcurrentDictionary class (here), I fell into one of the classic blunders that I myself always love to warn about. After analyzing the differences of time between a Dictionary with locking versus the new ConcurrentDictionary class, I noted that the… >>> More
What is the best retort to "premature optimization is the root of all evil"

as seen on Programmers - Search for 'Programmers'
Often I hear the sentiment ... "Why worry about performance, write slow code, get your product to market ... don't worry about performance. You can sort that out later" The culmination of this sentiment is: "... premature optimization is the root of all evil ... #winning" I was wondering, does… >>> More
Practical rules for premature optimization

as seen on Stack Overflow - Search for 'Stack Overflow'
It seems that the phrase "Premature Optimization" is the buzz-word of the day. For some reason, iphone programmers in particular seem to think of avoiding premature optimization as a pro-active goal, rather than the natural result of simply avoiding distraction. The problem is, the term is beginning… >>> More
Premature optimization is the root of all evil, but can it ever be too late?

as seen on Stack Overflow - Search for 'Stack Overflow'
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil" So what is that 3% like? Can the avoidance of premature optimization ever be taken too extreme that it does more harm than good? Even if it's rare, has there been a case of a… >>> More

Related posts about search

"Error in the Site Data Web Service." when performing crawl

as seen on Server Fault - Search for 'Server Fault'
Installed SharePoint Services v3 (SP2, october 2009 cumulative updates, Language Pack), attached to a content database I had previously (all works). Installed Search server 2008 Express (with language pack) on top of WSS and crawl does not work. However it works for newly created web application +… >>> More
Search Alternative Search Engines from within Bing’s Search Page

as seen on How to geek - Search for 'How to geek'
So you love using Bing Search but may still be curious to see what another search engine will provide if used. Now you can search using another search engine from within the Bing Search page and enjoy numbered results using two simple user scripts. Note: These user scripts may also be added to other… >>> More
CONVERT(int, (datepart(month, @search)), (datepart(day, @search)), DateAdd(year, Years.Year - (datepart(year, @search)))

as seen on Stack Overflow - Search for 'Stack Overflow'
In the query the top part is getting all the years that will run in the stored procedure. Works fine But at first i just wanted to run the queries for yesterdays date for all the years, but now i realized i want the user to select a date that will be in a parameter @search Booked <= CONVERT(int… >>> More
Am?lioration du Search MOSS: synonyme et Best Bet - La gestion des synonymes dans MOSS Search

as seen on ASP-PHP.net - Search for 'ASP-PHP.net'
Le moteur de recherche de MOSS permet la configuration d'une liste de synonymes. Nous verrons donc dans cet article comment effectuer cette tache et ce que cela peut apporter ? vos utilisateurs. Nous verrons aussi comment automatiser un peu plus cette configuration par l'utilisation de code ou d'outils… >>> More
Utiliser un MOSS 2007 Search avec SPS 2003 - Comment utiliser un MOSS Search avec SPS Portail

as seen on ASP-PHP.net - Search for 'ASP-PHP.net'
Microsoft Office SharePoint Server 2007 (MOSS) fournit de nombreuses fonctionnalit?s qui ne sont pas disponibles sous SharePoint Portal Server 2003 (SPS). C'est particuli?rement vrai pour le moteur de recherche. Ce moteur de recherche peut pourtant ?tre utilis? sans attendre une ?volution du site… >>> More