haskell - 寻找通用的 `bisect` 函数

Question

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

为此而胡闹:

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

不会产生任何结果。

某个库中是否有标准的通用二分搜索运算符？

Answer 1

罗斯帕特森的binary-search Hackage 上的包可以满足您的需求。具体参见searchFromTo ，具有类型签名

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

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

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