Posts

Showing posts from September, 2017

Binary Search in Haskell and Python 3.6

I've been learning a lot about Haskell lately, so I decided to write my own implementation of binary search after coming across Jacob Sheehy's implementation. In my own I wanted a nicer functional interface to locating a value in an entire list though. I also wanted it to be safe, using the Maybe monad in the event a value doesn't exist or the list is empty.
module Search where -- A humble implementation of binary search in Haskell binarySearch :: Int -> [Int] -> Maybe Int binarySearch _ [] = Nothing binarySearch value list = search 0 ((length list) - 1) where search :: Int -> Int -> Maybe Int search i j sublist = do if i > j then Nothing else do let midPoint = ((i + j) `quot` 2) currentValue = list !! midPoint -- compare outputs one of LT, GT, EQ case compare value currentValue of LT -> search i (midPoint - 1) GT -> search (midPoint + 1) j EQ -> Just mi…