二分查找 O(logn)
递归方法
int binarySearch1(int a[] , int low , int high , int findNum)
{
if (low > high)
return -1;
int mid = ( high - low ) / 2 + low;
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)
{
int mid;
while (low <= high)
{
mid = ( high - low ) / 2 + low; //此处一定要放在while里面
if (a[mid] < findNum)
low = mid + 1;
else if (a[mid] > findNum)
high = mid - 1;
else
return mid;
}
return -1;
}
代码中有两点值得注意：
中间值的写法mid = ( high - low ) / 2 + low而不要写成（high+low）/ 2
因为当搜索到最右边部分时，high+low有可能会是一个非常大的一个值，造成溢出，程序崩溃。非递归方法mid的定义放在while外面，如果放在while里，会重复分配内存。
