开发者社区> accompanymin> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

二分法优化

简介:
+关注继续查看

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


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
卡常优化
为卡常而生的三个函数 封装的快读
12 0
优化的扫雷
还是那个熟悉的味道,优化的扫雷,无限接近真正的扫雷。
35 0
优化代码
下图是老师在标准库中看到的一段代码的伪代码。问我们怎么优化。 老师说,c++程序员要对性能有敏感性。 有时候开源库性能进行了提升,并不一定是因为有了什么大改进,可能只是因为改进了类似下图中的代码而已。
760 0
SEO权重的优化1
1. 内部优化 a. 使用meta标签:比如title/keywords/description等优化 b. 内部链接的优化,包括相关性的连接(tag标签),锚文本、各导航链接,以及图片链接 c.
1327 0
接口优化
概述 推荐的分库分表中间件mycat 秒杀接口优化
874 0
凸函数优化
一、概率问题回顾:   无偏性:        样本均值和方差是总体的无偏估计:         均值的无偏性:        方差的无偏性:                凸优化:        凸优化的引入:        
931 0
项目优化
2017年6月9日 16:46:00 星期五 sql: 1. 统计出慢查询   . 索引优化   . 分表优化 2. 统计出程序中的所有sql   . 先大致看下有哪些是循环查库的优先解决掉, 减少查询数量   .
642 0
代码优化(一)
项目开发中代码书写很能够体现一个人的编程水平,这里记录自己的开发过程中遇到的编程的一些不良习惯,希望能够和打击共同提高。 1.接口方法中的代码不要超过300行。     --- 如果你发现自己接口中的方法超过300行的时候,就要考虑是否可以抽取公共的工具方法一起使用。
707 0
+关注
accompanymin
安心研究技术
6
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载