[Haskell-beginners] Re: Code help requested
Joe Van Dyk
joe at fixieconsulting.com
Fri Jan 15 19:17:55 EST 2010
Thanks all for your help.
Here's another one. Seems like I could use a fold here, but am unsure
how that would work. Also, if I pass in a search value that's too
big, then the function blows up.
(source at http://github.com/joevandyk/haskell/raw/master/pearls/binary_search/binary_search.hs
-- Feel free to fork it.)
-- A translation of
http://en.wikipedia.org/wiki/Binary_search_algorithm#Recursive
binary_find :: Ord a => [a] -> a -> Maybe Int
binary_find [] elem = Nothing
binary_find list elem =
do_search list elem 0 (length list)
where
do_search list elem low high =
if high < low then Nothing
else
if list !! mid > elem
then do_search list elem low (mid - 1)
else
if list !! mid < elem
then do_search list elem (mid + 1) high
else Just mid
where
mid = low + (high - low) `div` 2
main = do
print $ binary_find [1] 1
print $ binary_find [1,3] 1
print $ binary_find [1,3,4] 3
print $ binary_find [1,3,4] 4
print $ binary_find [1,2,4,6,8,9,12,15,17,20] 17
print $ binary_find "hello" 'l'
print $ binary_find [0.0, 1.5, 3.0] 3.0
print $ binary_find [] 1
print $ binary_find [1,3] 2
print $ binary_find [1,4,6,8,9,12,15,17,20] 2
-- boom?
print $ binary_find [1,4,6,8,9,12,15,17,20] 100
More information about the Beginners
mailing list