Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

ColobocCodeforces's blog

New binary search method
By ColobocCodeforces, history, 15 hours ago, In Russian

There is new method of binary search which may be exist but I didn't see it.

Instead of using left and right, we can simply add new bit to our answer if it is possible:

while bit > 0:
   if check(ans + bit): 
      ans += bit
   bit /= 2

Constant will be much smaller.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
14 hours ago, # |
  Vote: I like it -10 Vote: I do not like it

Oh yeah, let's make a blog for every fact that you didn't knew before. So, is that all what you've learned in your life? Pathetic.

→ Reply
  • »
    »
    8 hours ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Lol, why not? I haven't seen such implementation too, so for me this post is useful. There are too many useless blogs, but u've chosen this one))

    → Reply
»
8 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You can do better: create a new template function with multiple parameters: left, right, a function that returns true/false.

=> you don't need to write binary search never again (except few cases).

Like this (pseudocode):

    int binary_search<F>(int l, int r, F can) {
        int accum = l;
        int step = 1 << log2(r - l + 1);

        while step > 0 {
            if accum + step <= r && can(accum + step) {
                accum += step;
            }
            step >>= 1;
        }

        return accum;
    }
→ Reply