Re: Beginner Projects

Patricia Shanahan wrote:
Joshua Cranmer wrote:
Roedy Green wrote:
On Thu, 30 Aug 2007 00:32:11 -0400, Lew <lew@xxxxxxxxxxxxx> wrote,
quoted or indirectly quoted someone who said :

. OTOH, this counts as "premature optimization" in many cases.

It is simpler code, so I don't count it as optimisation. Optimisation
that gets you in trouble is verbose, harder-to-maintain code. I
figure every student should be familiar with odd/even idiom.

Sometimes it can save you.

int mid = (low + high) / 2;
int mid = (low + high) >>> 1;

The first one breaks when low + high > 2^31-1, the second one doesn't (only when low + high > 2^32 - 1).

Maybe there is something I'm not understanding here. I just did some
tests, and as far as I can tell, whenever they differ the first method
gets the right answer. Could you suggest some inputs that demonstrate
the benefit of the second version?

Results:

low=0, high=2147483647, mid1=1073741823, mid2=1073741823
! low=-5, high=-3, mid1=-4, mid2=2147483644
! low=-5, high=-2, mid1=-3, mid2=2147483644
low=-100, high=2147483647, mid1=1073741773, mid2=1073741773
! low=-2147483648, high=1000, mid1=-1073741324, mid2=1073742324
! low=-2147483648, high=2147483647, mid1=0, mid2=2147483647

Ah, the second one doesn't work for negative numbers.

Try using low = 1000, high = Integer.MAX_VALUE.

This was based on a mistaken implementation of the binary search algorithm.

--
Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
.