# 二進制搜索的遞歸函數

template
int orderedArrayListType::binarysearch
(const elemType& item) const
{
int first= 0;
int last = length -1;
int mid;
int list[];
int BinarySearch(,Type & Item, int first, int last)
bool found = false;
while (first <= last && !found){
mid = (first + last)/2;
if (list[mid] > item)
return BinarySearch(list, item, first, mid -1)
found = true;
else if (list[mid] > item)
return BinarySearch( list, item, first, mid -1)
last = mid - 1;
else
first = mid + 1;
}
if (found)
return mid;
else
return -1;
}


## 最佳答案

public class BinarySearchRecursive
{
public static final int NOT_FOUND = -1;

/**
* Performs the standard binary search
* using two comparisons per level.
* This is a driver that calls the recursive method.
* @return index where item is found or NOT_FOUND if not found.
*/
public static int binarySearch( Comparable [ ] a, Comparable x )
{
return binarySearch( a, x, 0, a.length -1 );
}

/**
* Hidden recursive routine.
*/
private static int binarySearch( Comparable [ ] a, Comparable x,
int low, int high )
{
if( low > high )
return NOT_FOUND;

int mid = ( low + high )/2;

if( a[ mid ].compareTo( x ) < 0 )
return binarySearch( a, x, mid + 1, high );
else if( a[ mid ].compareTo( x ) > 0 )
return binarySearch( a, x, low, mid - 1 );
else
return mid;
}

//Test program
public static void main( String [ ] args )
{
int SIZE = 8;
Comparable [ ] a = new Integer [ SIZE ];

for( int i = 0; i < SIZE; i++ )
a[ i ] = new Integer( i * 2 );

for( int i = 0; i < SIZE * 2; i++ )
System.out.println( "Found " + i + " at " +
binarySearch( a, new Integer( i ) ) );
}
}