ColobocCodeforces's blog

New binary search method
By ColobocCodeforces, history, 7 weeks 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
  • +12
  • Vote: I do not like it

»
7 weeks 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