Haskell Recipes

binsearch.hs

import Control.Applicative ((<$>), (<*>))

-- Binary Search
-- find the index of the given integer in the given sorted list
binsearch :: Int -> [Int] -> Maybe Int
binsearch _ [] = Nothing
binsearch v l  = case v `compare` middleValue of
  EQ -> Just middleIndex
  GT -> (+) <$> Just (middleIndex + 1) <*> binsearch v (take middleIndex l)
  LT -> binsearch v $ drop (middleIndex + 1) l
  where
    middleIndex = quot (length l) 2
    middleValue = l !! middleIndex