Search for the common `bisect` function

Question

I am looking for a bisect operation in Haskell similar to Python bisect_left() and friends. The input will be a lower bound, an upper bound, a non-decreasing function (Ord a) => (Int-> a), which must be defined for all integers between the lower and upper bound and the search value. The return value is the highest integer i , where lower <= i <= upper and f(i) < search_term . Performance should be O (log (n)).

Hoogling for this:

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

gives no results.

Is there a standard library search statement in a library somewhere?

Answer 1

Ross Paterson's binary-search package on Hackage does what you are looking for. In particular, see searchFromTo , which has a signature like

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

As Tikhon points out, [a] in Haskell is a linked list, not an array. Since linked lists only support sequential access, it is not possible to search by logarithmic time in the data structure [a] . Instead, you should use an authentic array data structure - see the vector library for a preferred implementation of arrays.

Dan Doel wrote a family of binary search functions for mutable vectors in a vector package: see Data.Vector.Algorithms.Search in his vector-algorithms library. Unlike the Ross Paterson library, which provides a clean API, the API in Data.Vector.Algorithms.Search is monadic (that is, it must be executed in the ST monad or IO monad).

Answer 2

A function like bisect_left (assuming I read its documentation correctly) does not really exist for lists.

This makes sense - since you don't have random access in O (1) in lists (remember that Haskell lists are linked by lists, while Python uses something more like a vector), you could not get an O (logn) binary search .

In particular, only getting into the middle of the list takes O (n / 2) steps (this is just O (n)) steps, therefore, an algorithm that includes the middle of the list (for example, binary search) should be in Ω (n).

In short - binary search does not make sense in lists. If you work a lot, you probably need a different data structure. In particular, see Data.Set , which internally uses binary trees.

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) 

(This may have a "one by one" error.)