Am Sonntag 17 Januar 2010 06:21:56 schrieb Steve:

On Sat, 2010-01-16 at 14:42 -0500, beginners-request@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