Java Binary Search help!

[bleedy3]

Here is the code for a binary search:

public static int BinSearch (int[]array, int searchNum){
int low = 0, high = array.length-1, mid = (low+high)/(2);
while(array[mid] != searchNum && low<= high ){
if(searchNum < array[mid])
high = mid -1;

else
low = mid+1;


mid = (low + high)/(2);

}

if(array[mid] != searchNum)
mid = -1;

return mid;

}

Can someone tell me the purpose of putting: low <= high, in the while statement because I don't see the reason. When would low be greater than high? It just doesn't make any sense.

[sourlemon]

First, you need to floor or ceil your mid so that it's always a whole number, else you'll get an exception.

Ex. If low = 0, high = 1. mid = (0 + 1)/2 = 0.5, which is not a correct index number to access an array.
-----------------------------------
To answer your question, if you keep increasing low and decreasing mid, of course they're going to meet. For example:

If you have an array of 5 numbers: {1, 2, 5, 6, 7}. Following the code, this is my initialization:

low = 0
high = 4
mid = (0 + 4)/2 = 2

Suppose you were looking for the number 3.
- Enter loop because array[2] != 3 && low(0) <= high(4)
- if(searchNum < array[mid]) (3 < 5) Yes
high = mid - 1 = 2 - 1 = 1.
- mid = (low + high)/(2);
mid = (1 + 0)/ 2 = 0.5. Suppose you floor this, so mid = 0.

Go through the loop again. searchNum (3) is now larger than array[mid] (array[0]), so you go with the second if statement.

low = mid + 1 = 0 + 1 = 1.
mid = (high+low)/2 = (1 + 1)/2 = 1.

Go through the loop again. And again, searchNum (3) is larger than array[mid] (array[1]), so you go with the second if statement.

low = mid + 1 = 1 + 1 = 2.
mid = (high+low)/2 = (1 + 2)/2 = 1 (flooring)

This essentially mean you have searched through the loop. So if you didn't have that low <= high, you'll continue with the loop forever. I hope that make some sense.

[bleedy3]

yea it does thanks