二分查找 θ(logn)
递归方法
int binarySearch1(int a[] , int low , int high , int findNum)
{
int mid = ( low + high ) / 2;
if (low > high)
return -1;
else
{
if (a[mid] > findNum)
return binarySearch1(a, low, mid - 1, findNum);
else if (a[mid] < findNum)
return binarySearch1(a, mid + 1, high, findNum);
else
return mid;
}
}
非递归方法
int binarySearch2(int a[] , int low , int high , int findNum)
{
while (low <= high)
{
int mid = ( low + high) / 2; //此处一定要放在while里面
if (a[mid] < findNum)
low = mid + 1;
else if (a[mid] > findNum)
high = mid - 1;
else
return mid;
}
return -1;
}
