[Haskell-beginners] Re: Code help requested

[Daniel Fischer]

Am Sonntag 17 Januar 2010 06:21:56 schrieb 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).

True - except I'm Out Of Memory long before overflow ;)

>
> Steve