通過掩碼進行二進制搜索？

Question

我已經多次使用這個算法在Ints或Longs上進行二分搜索。基本上，我從Long.MinValue和Long.MaxValue開始，並決定將位設置爲i th位置，具體取決於函數I正在最大化（或最小化）的值。實際上，這樣會更快（正好是63 * 2位操作），並且更容易編碼，並避免了許多gotchas of traditional binary search implementations。

這是我在斯卡拉算法：

/** 
* @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 S和Float s到工作之前的版本？

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 s。

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

再次，可能不是更有效率，但也許更多的斯卡拉樣。

UPDATE

您對智力/龍評論讓我想知道，如果一個函數可以做到這一切。

經過幾個死路，我終於想出了這個（奇怪的是，它實際上非常接近你的原始代碼）。

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

我不知道斯卡拉，但是這是我的版本的二進制搜索的通過在Java bitmasking
我的算法是這樣的

我們開始用的2月底和最大功率的指標在2 。我們每次更新itemIndex += index
迭代itemIndex後的時間我們看到
A[itemIndex] ≤ A[index]給出了項目的索引如果存在其他數組中給出了一個

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