Recursion Help?

Question

int binarySearch( int SortedArray[ ] , int key ){

if( SortedArray.length == 0 )
throw new ItemNotFound( "Binary Search fails: empty" );

int low = 0;
int high = SortedArray.length - 1;
int mid;

while( low < high )
{
mid = ( low + high ) / 2;

if( SortedArray[mid] < key )
low = mid + 1;
else
high = mid;
}

if( SortedArray[low] == key)
return low;

throw new ItemNotFound( "BinarySearch fails" );
}

What is the easiest way to make this one comparison per level Binary Search recursive? Thanks for any help.

Answer 1

read up on the binary search algorithm here: http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 2

int binarySearch(int[] sortedArray, int key){
if( SortedArray.length == 0 )
throw new ItemNotFound( "Binary Search fails: empty" );
return subArraySearch(sortedArray, key, 0, sortedArray.length-1);
}

int subArraySearch(int[] array, int key, int low, int high){
int mid = (low + high + 1)/2;

if (key == array[mid])
return mid;
else if (low == high) // One element in sub-array
throw new ItemNotFound( "BinarySearch fails" );
else if (key < array[mid])
return subArraySearch(array, key, low, mid-1);
else
return subArraySearch(array, key, mid+1, high);
}