binsearch.hs

Haskell

Public Domain

Perform a binary search on a list, returning either an element or an index

Download (right click, save as, rename as appropriate)

Embed

       

Tags:

binary binarySearch Haskell list search 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
binsearch :: (a -> Ordering) -> [a] -> Maybe a
binsearch cmp [] = Nothing
binsearch cmp list = case cmp (list !! i) of
 LT -> binsearch cmp (take i list)
 EQ -> Just (list !! i)
 GT -> binsearch cmp (drop (i+1) list)
 where i = length list `div` 2

binsearchIndex :: (a -> Ordering) -> [a] -> Maybe Int
binsearchIndex cmp [] = Nothing
binsearchIndex cmp list = case cmp (list !! i) of
 LT -> binsearchIndex cmp (take i list)
 EQ -> Just i
 GT -> i + 1 + binsearchIndex cmp (drop (i+1) list)
 where i = length list `div` 2