11.2 二分查找的原理及其实现

pow(2,10)=1024,所以只需要10次。二分查找的数必须为有序的。

#include<iostream>
using namespace std;

int BinarySearch(int a[], int n, int k)
{
	int left = 0;
	int right = n-1;
	while(left <= right)
	{
		int mid = left + (right - left)/2;
		if(a[mid] == k)
			return mid;
		else if(a[mid] > k)
			right = mid-1;
		else 
			left = mid + 1;			
	} 
	return -1;
} 

int main()
{
	int a[5]={1,2,5,7,9};//必须为有序的序列
	cout << BinarySearch(a,5,7) << endl;//3 
	return 0;
}

#include<iostream>
using namespace std;

int LowerBound(int a[], int n, int k)
{
	int left = 0;
	int right = n-1;
	int lowerk = -1;//赋初值，记录比k小的最大数的下标 
	while(left <= right)
	{
		int mid = left + (right - left)/2;
		if(a[mid] >= k)
			right = mid - 1;
		else
		{
			left = mid + 1;
			lowerk = mid;
		}
	} 
	return lowerk;
}

int main()
{
	int a[6] = {1,2,4,6,8,9};
	cout << LowerBound(a,6,7) << endl;//3 
	cout << LowerBound(a,6,9) << endl;//4
	return 0; 
}

L+R 的值可能很大，达到超过了int的范围，这样会导致溢出。