AFGhazy's blog

Binary Search without Infinite Loop
By AFGhazy, history, 9 years ago, In English

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.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think we can't use it on doubles.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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;

      → Reply
»
9 years ago, # |
  Vote: I like it -19 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it 
    // avoids addition overflow

    .. but introduces subtraction overflow.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bitmasking Then if you understood the topic good you may trace the code to know what the code is doing

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (1LL << i) = 2^i

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply