[Haskell-beginners] Re: Code help requested

[Steve]

On Sat, 2010-01-16 at 14:42 -0500, beginners-request at haskell.org wrote:
> 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.
mid = (low + high) `div` 2
is buggy code. Java had this bug for 9 years until someone noticed.
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

mid = low + (high - low) `div` 2
is useful because it avoids Int overflow errors (when using very, very
long lists).

Steve