Блог пользователя ColobocCodeforces

New binary search method
Автор ColobocCodeforces, история, 23 месяца назад, По-русски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
23 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем ColobocCodeforces (предыдущая версия, новая версия, сравнить).

→ Ответить
»
23 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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;
    }
→ Ответить