On very small arrays binary search loses - did so for years

On very small arrays binary search loses - did so for years

Posted Oct 24, 2007 20:29 UTC (Wed) by khim (subscriber, #9252)
In reply to: Missing: conventional wisdom turned into lie by JoeBuck
Parent article: Memory part 5: What programmers can do

If you just have 4-5 elements in the array then initial complexity of binary search will dominate - with or without memory access effects. At some point binary search will win - but it'll be good exercise to find this point today...

Actually it's true for most algorithms: bubble sort also wins for small arrays, for example. Usually trivial algorithms work well for small sizes but not-so-well for medium-to-large sizes. Usually it's not worth the effort to optimize for small sizes: it's fast not matter what algorithm you are using. If your program is spending 90% of time searchive 5-element arrays - it's different story, of course, but it's rare in practice...

---

(Log in to post comments)