Luke Stamper wrote:Winston...I was confused on how writing search methods for ints and strings. I was doing research and found one that I thought would work, but I don't think I fully understood how it worked.
Ah, I did wonder. Do you understand how the first one works now?
Luke Stamper wrote:Also, the midpoint formula you posted...is it correct because it accounts for negative numbers?
Sort of, although indexes can't be negative. The problem is that your formula can cause a numeric overflow if you have values for
first and
last that add up to more than
Integer.MAX_VALUE. That will result in a negative number which remains negative after the division and eventually leads to an ArrayIndexOutOfBoundsException. Obviously, the values have to be huge in order for it to happen, which is why the problem can (and
did) go undiscovered for a long time. The second formula prevents that from happening.
BTW: A faster alternative
in Java is:
int mid = (first + last) >>> 1;
I'll leave you to work out why.
Winston