Optimisation of std::binary_search of the <algorithm> header

[Tim Shen via libstdc++]

On Mon, May 29, 2017 at 1:05 AM, jay pokarna <jay.pokarna10@gmail.com> wrote:
>>> The technique that I have used is square root decomposition . I think
>>> that it will be better than the one that is implemented.
>>
>> And here's the problem: you *think* it will be better. Just thinking
>> is not enough. You need to *prove* it with benchmarks that show that
>> your technique is in fact faster than the current one.

Agreed.

Jay, specifically, your algorithm has the roughly the same running time:

  T(n) = log (sqrt(n) + 1) + log sqrt(n)
         > 2 log (n ^ 0.5)
         = 2 * 0.5 * log n
         = log n

It's unclear to me whether it's better than the normal binary search
or not. Detailed and representative benchmarks may convince more
people.


-- 
Regards,
Tim Shen