Am Samstag 16 Januar 2010 01:17:55 schrieb Joe Van Dyk:
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/bina ry_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)
That should be (length list - 1). binary_find [1] 2 ~> do_search [1] 2 0 1 ~> mid = 0 + 1 `div` 2 = 0 ~> [1] !! mid < 2 ~> do_search [1] 2 (0+1) 1 ~> mid = 1 + 0 `div` 2 = 1 ~> [1] !! 1 => boom
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
I'd prefer mid = (low + high) `div` 2 here.
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
However: Lists are _not_ arrays. list !! n is O(n), except n >= length list, then getting the error is O(length list). And getting the length is O(length list), too. So the binary search on list is O(l*log l), where l = length list, while straightforward linear search is O(l). You can make the binary search O(l) if you have binaryFind list e = search list e (length list) where search _ _ 0 = Nothing search lst e len | x == e = Just e | x < e = search front e half | otherwise = search back e (len - half - 1) where half = (len - 1) `div` 2 (front, x:back) = splitAt half lst but in general, that is still much worse than straightforward search. The binary search algorithm is for data structures with constant time access (arrays, anything else?), not singly linked lists. foldSearch list e = foldr f Nothing list where f x y | x == e = Just x | otherwise = y