Logo

Programming-Idioms

History of Idiom 124 > diff from v20 to v21

Edit summary for version 21 by Alekzcb:
[Haskell] accidentally a line
↷

Version 20

2017-09-21, 18:06:37

Version 21

2017-09-21, 18:07:58

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
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 binSearch t a
                else if t > m then aux (binSearch t b)
                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. aux serves to add Maybes together.

Ord is used to allow use of < and >.

t is the target to search for and l is the list.
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. aux serves to add Maybes together.

Ord is used to allow use of < and >.

t is the target to search for and l is the list.