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)
Andrew | 06-Dec-09 at 1:41 am | Permalink
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)