One against binary searches

[Xinok]

On Monday, 30 July 2012 at 17:20:54 UTC, bearophile wrote:
> Xinok:
>
>> My stable sort makes heavy use of binary searches [1], so just 
>> for fun, I tried inserting a ternary search before the binary 
>> search.
>
> I think in the end he suggests to use a "offseted binary" or a 
> "quaternary search", over both binary and ternary searches (if 
> the array is not too much small).

An offseted binary search wouldn't work in this case. The "binary 
search" is actually comparing elements in two adjacent ranges 
which are equidistant from the center, so it's impossible to 
align in both ranges.

I also tried a quaternary search, but it was 25-30ms slower than 
a ternary search, albeit it was a bit faster than a binary search.