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

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 个问题：

这个算法在文献中叫什么？当然，我不可能是这个的发明者 - 但是，当我尝试使用谷歌搜索二进制搜索 + bit-masking/toggling 的各种组合时，我没有找到任何东西。我个人一直称它为"bitBinSearch"。在对 Int 或 Long 域进行二分搜索的文章中，我根本没有看到这一点，在这些文章中写起来很简单。
代码可以是improved/shortened吗？现在，我跟踪 n 和 p 中的负解和正解。有什么巧妙的方法可以将它们合并为单个变量吗？以下是一些示例测试用例：http://scalafiddle.net/console/70a3e3e59bc61c8eb7acfbba1073980c 在您尝试回答之前
是否有可以与 Doubles 和 Floats 一起使用的版本？

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

当然，如果你进行递归，你可以消除那些讨厌的 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)
}

同样，可能没有更高效，但可能更像 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)

Answer 2

我不懂 Scala，但这是我在 java 中通过位掩码进行二进制搜索的版本
我的算法是这样的

我们从 2 的最高幂的索引开始，到 2⁰ 结束。每次我们看到
A[itemIndex] ≤ A[index] 我们更新 itemIndex += index
迭代后 itemIndex 给出项目的索引（如果存在于数组中）否则给出 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;
}

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

Binary searching via bitmasking?

algorithm

scala

bit-manipulation

binary-search

bitmask