二分法优化

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;
}