正在查找泛型“bisect`”函数

Question

我正在寻找一个类似于Python的bisect_left()和朋友的Haskell的bisect操作。输入将是一个下界、一个上界、一个非递减函数(Ord )=>(Int->a)(必须为介于上下界之间的所有整数定义)和一个搜索值。返回值是最大整数i，其中lower <= i <= upper和f(i) < search_term。性能应该是O(log(n))。

为此而胡扯：

(Ord a)=>(Int->a)->Int->Int->a->Int

不会产生任何结果。

在某个库中有没有标准的、通用的二进制搜索运算符？

Answer 1

罗斯·帕特森关于Hackage的binary-search包做了你想要的。具体地说，请参见具有类型签名的searchFromTo

searchFromTo :: Integral a => (a -> Bool) -> a -> a -> Maybe a

正如Tikhon指出的那样，Haskell中的[a]是一个链表而不是数组。由于链表只支持顺序访问，因此不可能在[a]数据结构上进行对数时间搜索。相反，您应该使用真正的数组数据结构--有关数组的首选实现，请参阅vector库。

Dan Doel为向量包中的可变向量编写了一系列二进制搜索函数:请参阅他的vector-algorithms库中的Data.Vector.Algorithms.Search。与Ross Paterson提供纯API的库不同，Data.Vector.Algorithms.Search中的API是一元的(也就是说，它必须在ST monad或IO monad中运行)。

Answer 2

像bisect_left这样的函数(假设我没看错它的文档)不能真正存在于列表中。

这是有道理的--因为您在列表中没有O(1)的随机访问(请记住，Haskell列表是链表，而Python使用更像向量的东西)，您不可能真正得到O(logn)的二进制搜索。

特别是，仅仅到达列表的中间就需要O(n/2) (这只是O(n))个步骤，所以涉及列表中间的算法(如二进制搜索)必须在Ω(n)中。

简而言之，二进制搜索在列表上没有意义。如果你要进行大量的搜索，你可能需要一个不同的数据结构。特别是，看看内部使用二叉树的Data.Set。

Answer 3

binary_search :: Ord a, Integral b => (b -> a) -> b -> b -> a -> b
binary_search f low hi a = go low hi
     where
        go low hi | low + 1 == hi = low
        go low hi = go low' hi'
           where
              mid = (low + hi) `div` 2
              (low',hi') = if f mid < a then (mid,hi) else (low, mid)

(这可能存在off-by-one错误。)