[Haskell-beginners] Re: Code help requested
Tim Perry
perry2of5 at yahoo.com
Fri Jan 15 20:17:24 EST 2010
Hi Joe,
I think you wanted (length list - 1) where you call do_search. The version below is my rewrite with guards, this change, and "midVal" which keeps "list !! mid" from being evaluated twice per recursion. Unfortunately, I have no idea how to work a fold into this. Good luck!
--Tim
binary_find :: Ord a => [a] -> a -> Maybe Int
binary_find [] elem = Nothing
binary_find list elem =
do_search list elem 0 (length list -1)
where
do_search list elem low high
| high < low = Nothing
| midVal > elem = do_search list elem low (mid - 1)
| midVal < elem = do_search list elem (mid + 1) high
| otherwise = Just mid
where
midVal = list !! mid
mid = low + (high - low) `div` 2
main = do
print $ binary_find [1] 2
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] 19
More information about the Beginners
mailing list