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

[jay pokarna <jay dot pokarna10 at gmail dot com>]

Respected Sir,
                         Could you give me the contact of the standard
committee which handles changes to the c++ standard.

Regards,
Jay Pokarna

On Mon, May 29, 2017 at 2:17 PM, Tim Shen <timshen@google.com> wrote:
> 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



-- 
Regards,
Jay Pokarna
CS Sophomore
Wordpress | Linkedin
Birla Institute of Technology and Science, Pilani
Pilani Campus
Rajasthan - 333031.