Logo

Programming-Idioms

History of Idiom 124 > diff from v18 to v19

Edit summary for version 19 by Alekzcb:
New Haskell implementation by user [Alekzcb]
↷

Version 18

2016-06-17, 21:36:45

Version 19

2017-09-21, 18:04:49

Idiom #124 Binary search for a value in sorted array

Write function binarySearch which returns the index of an element having value x in sorted array a, or -1 if no such element.

Idiom #124 Binary search for a value in sorted array

Write function binarySearch which returns the index of an element having value x in sorted array a, or -1 if no such element.

Extra Keywords
dichotomic dichotomy
Extra Keywords
dichotomic dichotomy
Code 
binSearch :: Ord a => a -> [a] -> Maybe Int
binSearch _ [] = Nothing
binSearch t l = let n = div (length l) 2
                    (a, m:b) = splitAt n l in
                if t < m then aux (binSearch t a)
                else Just n where
    aux :: Maybe Int -> Maybe Int
    aux (Just x) = Just (x+n+1)
    aux _ = Nothing
Comments bubble
Haskell promotes using data structures rather than special values to indicate failures, so I have opted to use Maybe rather than return -1. Ord is used to allow use of _< and _>.