二分法优化

简介:

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


相关文章
|
人工智能 算法
【算法分析与设计】递归与分治策略(二)
【算法分析与设计】递归与分治策略
|
算法
快排三种递归及其优化,非递归和三路划分
快排三种递归及其优化,非递归和三路划分
77 0
|
机器学习/深度学习 算法 编译器
【算法分析与设计】递归与分治策略(一)
【算法分析与设计】递归与分治策略
|
9月前
|
搜索推荐
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
98 0
|
9月前
|
算法 C++
动态规划的时间复杂度优化
动态规划的时间复杂度优化
|
算法 搜索推荐
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
分治法实现合并排序(归并排序),理解分治算法思想,实现分治算法的完美例子合并排序(含码源与解析)
224 0
|
算法
算法分析与设计——递归算法(二)1.汉罗塔问题
算法分析与设计——递归算法(二)1.汉罗塔问题
|
算法
算法分析与设计——递归算法(一)
算法分析与设计——递归算法(一)
|
算法 搜索推荐 Windows
【算法分析与设计】递归与分治策略(三)
【算法分析与设计】递归与分治策略
|
算法 Go 索引
870. 优势洗牌:田忌赛马:贪心算法+双指针
这是 力扣上的 870. 优势洗牌,难度为 中等。
325 0

热门文章

最新文章