title: Binary searching via bitmasking?
body: <p>I have used this algorithm many times to binary search over <code>Ints</code> or <code>Longs</code>. Basically, I start from <code>Long.MinValue</code> and <code>Long.MaxValue</code> and decide to set the bit at <code>i</code>th 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 <a href="https://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search">gotchas of traditional binary search implementations</a>.</p>
  
  <p>Here is my algorithm in Scala:</p>
  
  <pre><code>/**
   * @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 =&gt; Boolean): Option[Long] = {
    var n = 1L &lt;&lt; 63
    var p = 0L
    for (i &lt;- 62 to 0 by -1) {
      val t = 1L &lt;&lt; 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
  }
  </code></pre>
  
  <p>I have 3 questions:</p>
  
  <ul>
  <li><p>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 <code>Int</code> or <code>Long</code> domain where this would be trivial to write.</p></li>
  <li><p>Can the code be improved/shortened in anyway? Right now I keep track of the negative and positive solutions in <code>n</code> and <code>p</code>. Any clever way I can merge them  into single variable? Here are some sample test cases: <a href="http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c" rel="nofollow noreferrer">http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c</a> before you attempt an answer</p></li>
  <li><p>Is there a version that can be made to work with <code>Double</code>s and <code>Float</code>s?</p></li>
  </ul>