Recursion Help
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.
[792 byte] By [
EHump20] at [2007-11-11 10:25:45]
# 1 Re: Recursion Help
A way to do this is to explicitly name the range of your search:
int binarySearch( int SortedArray[], int low, int high, int key )
it's a good idea to set your base case, first:
if(SortedArray[mid] == key)
{
return mid;
}
Then, to continue your search, break the potential into two cases
while( low < high )
{
if( SortedArray[mid] < key )
{
low = mid + 1;
return binarySearch( int SortedArray[], int low, int high, int key );
}
else
{
high = mid - 1;
return binarySearch( int SortedArray[], int low, int high, int key );
}
}
throw new ItemNotFound( "BinarySearch failed" );
}
nspils at 2007-11-11 20:58:51 >
