4 ms·
However, if you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects, you can't beat binary search. ... if
by cperciva 16y ago
However, if you're given an array of unknown objects, a comparison function, and no way to do arithmetic on your objects, you can't beat binary search.
... if all you care about is operation count. If you're fetching pages from disk, a B+Tree will perform dramatically better than a binary search.
And if you're fetching pages from disk and have a large cache, a B+Tree can do far better than interpolation search, too. Interpolation search will thrash your cache, resulting in O(log log n) seeks, whereas a cache of size O(n/B) will allow a B+Tree to find data in O(1) seeks.
- RiderOfGiraffes 16y agoBut now you're talking about different data structures - his assumption was that you had a simple sorted array. We both know that there's a lot that can be done, and when performance really matters you don't use a sorted array, you don't use binary search, and you do take into account things like access pattern, access speed, caches, etc. But people don't, because they read simplistic articles like this and then believe they know everything. At least the author could hint that there's a lot more that can be done. As it is, it just leaves the naive reader with a sense that they've seen the light, and the experienced reader irritated.
- cperciva 16y agoTrue. Although I'd be interested in seeing actual benchmarks for interpolation vs. binary search too, since binary search has better cache locality...