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

Binary Search without Infinite Loop
Автор AFGhazy, история, 9 лет назад, По-английски

Hey, Codeforces I suffered for awhile from writing efficient codes for binary searching, but recently I found an efficient way using bit masking. Say you want to maximize a result using binary search and good function that return true if it's oky or false otherwise. so our binary search would be like that:

__int64 r = 0; for(int i = 62; i >= 0; --i) { if( good(r + (1LL<<i)) ) r += (1LL<<i); }

now you can binary search with out usage of variables such as low and high and middle which would lead to infinite loops.

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As I know it's called binary lifting, btw lower_bound and upper_bound in c++ stl uses same approach)

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Hmmmm...Nice...I didn't see that before...

Can we always use this instead of binary search???

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think we can't use it on doubles.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится

      i think it'll be fine if you do it like this
      for (long double gap = (1LL << 62); gap > eps; gap /= 2)
      if (good(r + gap))
      r += gap;

      → Ответить
»
9 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

А как писать левый бианрный поиск таким подходом???

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

We can modify the classic binary search to avoid these bugs.

inline int binarySearch(int v[], int n, int x)
{
    int lo = -1, hi = n, mid;     // we set both hi and lo outside our range of search

    while (hi - lo > 1)           // this invariant will keep lo and hi distinct
    {
        mid = lo + (hi - lo) / 2; // avoids addition overflow
        if (v[mid] < x)           // invariant v[lo] < x <= v[hi], assuming v[-1] = -oo and v[n] = oo
            lo = mid;
        else
            hi = mid;
    }
    if (hi == n || v[hi] != x)    // not found
        return -1;
    return x;                     // found
}

You can read more about it here.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится 
    // avoids addition overflow

    .. but introduces subtraction overflow.

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Assuming n is non-negative, hi is always greater than lo. So, how would that line cause an overflow?

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        If I am correct, since you have lo = -1 at beginning, if hi were maximum positive value for "int" i.e. hi = [(1L << 31) — 1] Then (hi — lo) would evaluate to (hi + 1) = (1 << 31) = -2147483648. And for 32 bit signed integer, it would turn negative. But who would use such hi value?

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
int result = -1; // remains -1 if no argument is good
while (left <= right) {
  int mid = (left + right) / 2;
  if (good(mid)) {
    result = mid;
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

No infinite loops, no bugs, no thinking, only AC at the first attempt.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Can you elaborate a bit.And what is good(mid),a predicate function ?

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      Yes, it's a predicate function, what else can it be.

      The main advantage of this version of binary search is that it always saves its structure. No unclear "invariants" with all these half-opened segments, which usually are the causes of bugs. The fact that result variable is updated as the search goes on, makes it easy to manage.

      The code above assumes that the function good() is non-increasing (1, ..., 1, 0, ..., 0). Now, say, it's non-decreasing (0, ..., 0, 1, ..., 1). Then just swap the lines left = mid + 1 and right = mid - 1 and it's done!

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        No idea why you've got minuses, but thank you for the most understandable and predictable binary search I've ever seen.

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks, I've always been using recursive binary search and this has opened my eyes.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I didn't got it what should i konw to understand this code?

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have no idea about bit masking but i found this article very helpful to clearly understand binary search.

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

Here's a clean Scala version that also works for negative numbers:

 /**
   * Binary search by bit toggling from MSB to LSB
   * O(64) bit-wise operations for Longs (O(32) for Ints)
   *
   * @return Some(x) such that x is the largest number for which f is true
   *         If no such x is found, None
   */
  def bitBinSearch(f: Long => Boolean): Option[Long] = {
    var p = 0L
    var n = Long.MinValue
    var t = n >>> 1
    while (t > 0) {
      if (f(p|t)) p |= t
      if (f(n|t)) n |= t
      t >>= 1
    }
    Seq(p, n) find f
  }

Source: https://github.com/pathikrit/scalgos/blob/c7f79824a4110397cbf340c08cae487b00ba7677/src/main/scala/com/github/pathikrit/scalgos/BitHacks.scala#L90

→ Ответить