[Haskell-beginners] Re: Code help requested

[Daniel Fischer]

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