Binary Search in Haskell

I have just written a function in Haskell that will perform a binary search on a list of integers. Pass it your list, the value you’re searching for, default low and high (0 and n-1) and it will return for you the position of your value. I’m sure there are plenty of experienced Haskell coders that will tell me there’s a better way, but I haven’t heard from one yet.

binsearch :: [Int] -> Int -> Int -> Int -> Int -- list, value, low, high, return int
binsearch xs value low high
   | high < low       = -1
   | xs!!mid > value  = binsearch xs value low (mid-1)
   | xs!!mid < value  = binsearch xs value (mid+1) high
   | otherwise        = mid
   where
   mid = low + ((high - low) `div` 2)

3 thoughts on “Binary Search in Haskell

  1. You could make your function a tad more general:

    binsearch :: (Ord a) => [a] -> a -> Int -> Int -> Maybe Int — list, value, low, high, return int
    binsearch xs value low high
    | high value = binsearch xs value low (mid-1)
    | xs!!mid < value = binsearch xs value (mid+1) high
    | otherwise = Just mid
    where
    mid = low + ((high – low) `div` 2)

  2. There is no point of doing a binary search on a list, because it takes O(n*log(n)) time, whereas a linear search takes O(n) time. You should change the binary search to an array. This is simply a matter of replacing !! with !. e.g.:

    import Data.Array;

    binarySearch haystack needle lo hi
    | hi needle = binarySearch haystack needle lo (mid-1)
    | pivot < needle = binarySearch haystack needle (mid+1) hi
    | otherwise = Just mid
    where
    mid = lo + (hi-lo) `div` 2
    pivot = haystack!mid

  3. stupid html. i meant:

    import Data.Array;

    binarySearch haystack needle lo hi
    | hi < lo = Nothing
    | pivot > needle = binarySearch haystack needle lo (mid-1)
    | pivot < needle = binarySearch haystack needle (mid+1) hi
    | otherwise = Just mid
    where
    mid = lo + (hi-lo) `div` 2
    pivot = haystack!mid

Leave a Reply

Your email address will not be published. Required fields are marked *