二分法优化

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