Binary searching via bitmasking?

Question

I have used this algorithm many times to binary search over Ints or Longs. Basically, I start from Long.MinValue and Long.MaxValue and decide to set the bit at ith position depending on the value of the function I am maximizing (or minimizing). In practice, this turns out to be faster (exactly 63*2 bitwise operations) and easier to code and avoids the many gotchas of traditional binary search implementations.

Here is my algorithm in Scala:

/**
 * @return Some(x) such that x is the largest number for which f(x) is true
 *         If no such x is found, return None
 */
def bitBinSearch(f: Long => Boolean): Option[Long] = {
  var n = 1L << 63
  var p = 0L
  for (i <- 62 to 0 by -1) {
    val t = 1L << i
    if (f(n + t)) n += t
    if (f(p + t)) p += t
  }
  if (f(p)) Some(p) else if (f(n)) Some(n) else None
}

I have 3 questions:

• What is this algorithm called in literature? Surely, I can't be the inventor of this - but, I did not find anything when I tried googling for various combinations of binary-search + bit-masking/toggling. I have been personally calling it "bitBinSearch". I have not seen this mentioned at all in articles going over binary search over an Int or Long domain where this would be trivial to write.

• Can the code be improved/shortened in anyway? Right now I keep track of the negative and positive solutions in n and p. Any clever way I can merge them into single variable? Here are some sample test cases: http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c before you attempt an answer

• Is there a version that can be made to work with Doubles and Floats?

Answer 1

As long as you're bit-twiddling (a popular pastime in some circles) why not go all the way? I don't know if there's any efficiency to be gained, but I think it actually makes the algorithm a little clearer.

def bitBinSearch(f: Long => Boolean): Option[Long] = {
  var n = Long.MinValue
  var p = 0L
  var t = n >>> 1
  while (t > 0) {
    if ( f(n|t) ) n |= t
    if ( f(p|t) ) p |= t
    t >>= 1
  }
  List(p,n).find(f)
}

Of course, if you go recursive you can eliminate those nasty vars.

import scala.annotation.tailrec
@tailrec
def bitBinSearch( f: Long => Boolean
                , n: Long = Long.MinValue
                , p: Long = 0L
                , t: Long = Long.MinValue >>> 1 ): Option[Long] = {
  if (t > 0) bitBinSearch(f
                         , if (f(n|t)) n|t else n
                         , if (f(p|t)) p|t else p
                         , t >> 1
                         )
  else List(p,n).find(f)
}

Again, probably not more efficient, but perhaps a bit more Scala-like.

UPDATE

Your comment about Int/Long got me wondering if one function could do it all.

After traveling down a few dead-ends I finally came up with this (which is, oddly, actually pretty close to your original code).

import Integral.Implicits._
import Ordering.Implicits._
def bitBinSearch[I](f: I => Boolean)(implicit ev:Integral[I]): Option[I] = {
  def topBit(x: I = ev.one):I = if (x+x < ev.zero) x else topBit(x+x)
  var t:I = topBit()
  var p:I = ev.zero
  var n:I = t+t
  while (t > ev.zero) {
    if ( f(p+t) ) p += t
    if ( f(n+t) ) n += t
    t /= (ev.one+ev.one)
  }
  List(p,n).find(f)
}

This passes the following tests.

assert(bitBinSearch[Byte] (_ <= 0) == Some(0))
assert(bitBinSearch[Byte] (_ <= 1) == Some(1))
assert(bitBinSearch[Byte] (_ <= -1) == Some(-1))
assert(bitBinSearch[Byte] (_ <= 100) == Some(100))
assert(bitBinSearch[Byte] (_ <= -100) == Some(-100))
assert(bitBinSearch[Short](_ <= 10000) == Some(10000))
assert(bitBinSearch[Short](_ <= -10000) == Some(-10000))
assert(bitBinSearch[Int]  (_ <= Int.MinValue) == Some(Int.MinValue))
assert(bitBinSearch[Int]  (_ <= Int.MaxValue) == Some(Int.MaxValue))
assert(bitBinSearch[Long] (_ <= Long.MinValue) == Some(Long.MinValue))
assert(bitBinSearch[Long] (_ <= Long.MaxValue) == Some(Long.MaxValue))
assert(bitBinSearch[Long] (_ < Long.MinValue) == None)

Answer 2

I don't know Scala, but this is my version of Binary searching via bitmasking in java
My algorithm is like this

We start with the index with highest power of 2 and end at 2⁰. Every time we see
A[itemIndex] ≤ A[index] we update itemIndex += index
After the iteration itemIndex gives the index of the item if present in the array else gives the floor value in A

int find(int[] A, int item) { // A uses 1 based indexing
    int index = 0;
    int N = A.length;
    for (int i = Integer.highestOneBit(N); i > 0; i >>= 1) {
        int j = index | i;
        if (j < N && A[j] <= item) {
            index = j;
            if (A[j] == item) break;
        }
    }
    return item == A[index] ? index : -1;
}