二分法优化-阿里云开发者社区

开发者社区> 人工智能> 正文

二分法优化

简介:

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


版权声明:本文首发在云栖社区,遵循云栖社区版权声明:本文内容由互联网用户自发贡献,版权归用户作者所有,云栖社区不为本文内容承担相关法律责任。云栖社区已升级为阿里云开发者社区。如果您发现本文中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,阿里云开发者社区将协助删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章