[Haskell-beginners] Re: Code help requested
Daniel Fischer
daniel.is.fischer at web.de
Fri Jan 15 20:00:10 EST 2010
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
More information about the Beginners
mailing list