algorithm - 通过位掩码进行二进制搜索？

Question

我多次使用这个算法对 Ints 或 Longs 进行二分查找。基本上，我从 Long.MinValue 和 Long.MaxValue 开始，并决定根据函数的值将位设置在第 i 位置我正在最大化(或最小化)。在实践中，事实证明这更快(恰好 63*2 位运算)并且更容易编码并且避免了许多 gotchas of traditional binary search implementations .

这是我在 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
}

我有 3 个问题:

• 这个算法在文献中叫什么？当然，我不能成为这个的发明者 - 但是，当我尝试使用谷歌搜索二进制搜索 + 位掩码/切换的各种组合时，我没有找到任何东西。我个人一直称它为“bitBinSearch”。在对 Int 或 Long 域进行二分搜索的文章中，我根本没有看到这一点，在这些文章中，编写这将是微不足道的。

• 代码是否可以改进/缩短？现在，我跟踪 n 和 p 中的负解和正解。有什么巧妙的方法可以将它们合并为单个变量吗？以下是一些示例测试用例:http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c在你尝试回答之前

• 是否有可以与 Double 和 Float 一起使用的版本？

Answer 1

只要你在玩弄(某些圈子里流行的消遣)，为什么不一路走下去呢？我不知道是否可以提高效率，但我认为它实际上使算法更清晰一些。

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)
}

当然，如果你进行递归，你可以消除那些讨厌的 var。

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)
}

同样，可能不会更高效，但可能更像 Scala。

更新

您对 Int/Long 的评论让我想知道是否一个函数可以完成所有工作。

在走了几个死胡同之后，我终于想到了这个(奇怪的是，它实际上非常接近您的原始代码)。

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)
}

这通过了以下测试。

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)