I'm trying to implement a recursive binary search, after looking at the example on this textbook page.
My algorithm seems to work fine in most cases, but on values higher than the highest value in the array, I get an ArrayIndexOutOfBoundsException. Looking at my algorithm and the textbook example, they seem identical; can someone help me find where I've gone wrong?
I'm aware this is mostly the same issue as in this thread, and I have already considered the solution it proposes. The example code however, does not implement any argument correction like this, and I wonder why it works without it.
public static int binarySearch(int[] array, int item, int lowPos, int highPos){
if (lowPos > highPos){
return -1;
}
int mid = (lowPos + highPos)/2;
if (array[mid] == item){
return mid;
}else if (array[mid] > item){
return binarySearch(array, item, lowPos, mid-1);
}else{
return binarySearch(array, item, mid+1, highPos);
}
}
This is the textbook example, which obviously does not produce the error:
static int binarySearch(int[] A, int loIndex, int hiIndex, int value) {
if (loIndex > hiIndex) {
// The starting position comes after the final index,
// so there are actually no elements in the specified
// range. The value does not occur in this empty list!
return -1;
}
else {
// Look at the middle position in the list. If the
// value occurs at that position, return that position.
// Otherwise, search recursively in either the first
// half or the second half of the list.
int middle = (loIndex + hiIndex) / 2;
if (value == A[middle])
return middle;
else if (value < A[middle])
return binarySearch(A, loIndex, middle - 1, value);
else // value must be > A[middle]
return binarySearch(A, middle + 1, hiIndex, value);
}
} // end binarySearch()
binarySearchmethod from your client class/method e.g.public static void main(String[] args).