C怎样语言实现如下算法?
C怎样语言实现如下算法?
从键盘输入10个数的有序数列。然后,再输入一个数,用折半查找法在数列中查找。如果找到,输出" FOUND",并输出该 数列中的位置。如没找到,则输出"NOT FOUND"
[解决办法]
输入的序列都已经是有序的了?那就直接binary search吧,c++实现一个:
template <typename Comparable>
int binarySearch( const vector<Comparable> & a, const Comparable & x )
{
int low = 0, high = a.size( ) - 1;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( a[ mid ] < x )
low = mid + 1;
else if( a[ mid ] > x )
high = mid - 1;
else
return mid; // Found
}
return NOT_FOUND; // NOT_FOUND is defined as -1
}
[解决办法]