二分法优化

1,基本的二分思想：

int BinarySearch(int a[],int size,int key){   int L = 0; //查找区间的左端点   int R = size - 1; //查找区间的右端点   while( L <= R) { //如果查找区间不为空就继续查找   int mid = L+(R-L)/2; //取查找区间正中元素的下标   if( key == a[mid] )       return mid;   else if( key > a[mid])       L = mid + 1; //设置新的查找区间的左端点   else       R = mid - 1; //设置新的查找区间的右端点   }   return -1;}

其实:L+(R-L)/2=(R+L)/2

为了防止（L+R）溢出，才这样写（出于ACM的需要）

2，将L  R的初始化边界扩展1

int internalFor(int a[], int l, int r, int key) {//二分法查找a[] l到r区间的某个值	int L = l - 1;	int R = r + 1;	int mid;	while (R - L > 1) {//不能设置等于		mid = L + (R - L) / 2;		if (a[mid] > key) {			R = mid;		}		if (a[mid] < key) {			L = mid;		}		if (a[mid] == key) {			return mid;		}	}	return -1;}

3，二分算法用于不等式范围查找：

int bs_nomorethan(int a[], int l, int r, int key) {//寻找小于等于key的元素的个数	int L = l - 1;	int R = r + 1;	int mid;	while (R - L > 1) {		mid = L + (R - L) / 2;		if (a[mid] <= key) {			L = mid;		}		if (a[mid] > key) {			R = mid;		}	}	return L;}

4，基于二分法思想的左右线性移动查找：

void ArrayTwoNumberAdd(int a[], int size,int sum) {//使用两边移动桶的方式，进行对数组的两个数之和进行判断	int L = 0;	int R = size - 1;	int num = 0;	while (L <= R) {		if (a[L] + a[R] > sum) {			R--;		}		if (a[L] + a[R] < sum) {			L++;		}		if (a[L] + a[R] == sum) {			cout << a[L] << "+" << a[R] << "=" << sum << endl;			L++;			R--;			num++;		}	}	cout << "总共有个：" << num << "对" << endl;}