One against binary searches

[Andrei Alexandrescu]

On 7/30/12 1:28 PM, Don Clugston wrote:
> On 30/07/12 17:40, bearophile wrote:
>> This author writes very detailed analyses of low-level computational
>> matters, that appear on Reddit. This blog post he suggests to introduce
>> "offseted binary" or "quaternary search" instead of binary search in
>> Phobos:
>>
>> http://www.pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/
>>
>>
>>
>> Bye,
>> bearophile
>
> Fantastic article, thanks!
> The fact that physical addressing can influence L2 cache misses was
> completely new to me.

BTW we have alternative searches in sorted ranges that are 
cache-friendly in Phobos, trot and gallop (backwards and forwards): 
http://dlang.org/phobos/std_range.html. They work well if there's a good 
assumption that the searched item is toward the beginning or the end of 
the range, and galloping search has O(log n) complexity.

Andrei