程序设计与算法（二）：3. 二分算法

2021-12-15 23:02:58

例查找p

例查找lowerbound

例二分法求方程的根

例找一对数

例农夫和奶牛

例子源于慕课课程：程序设计与算法二

二分查找：有序、时间复杂度是log(n)

例查找p

int BS(int a[], int size, int p) {
	int low = 0, high = size - 1;
	while (low <= high) {
		int mid = (low + high) / 2;

		if (a[mid] == p)
			return a[mid];
		else if (a[mid] < p) low = mid + 1;
		else high = mid - 1;
	}
	return -1;
}

例查找lowerbound

代码

int BS(int a[], int size, int p) {
	int low = 0, high = size - 1;
	int lastposition = -1;//最优解的下标
	while (low <= high) {
		int mid = (low + high) / 2;
		if (a[mid] >= p)
			high = mid - 1;
		else {
			lastposition = mid;
			low = mid + 1;
		}
	}
	return lastposition;
}

注意

1. 从课程中学到mid=(low+high)/2有溢出的风险，可能(low+high)超出int的范围

2. 改成 mid=low+(high-low)/2;

3. 接下来取中点的代码都是改后的

例二分法求方程的根

步骤是固定的

确定单调性，本题是单调递增
确定区间长度合适的有根区间，[0,100],f(0)<0,f(100)>0,root=(x1+x2)/2
如果f(root)<0,新的区间为[root,x2]
否则新的区间为[x1,root]
注意只要得出满足精度条件（EPS=1e-6）的解即可

补充

1. fabs()函数：返回某一个值的绝对值的一个函数
例如，fabs(x)就是返回x的绝对值
2. fabs的参数为double型,返回值也是double型abs的参数为int型,返回值也是int型。
abs是求一个整数的绝对值,而fabs是求一个实数的绝对值。

代码

#define EPS 1e-6
double f(double x) { return x * x * x - 5 * x * x + 10 * x - 80; }

int main() {
	double x1 = 0, x2 = 100;
	double root = x1 + (x2 - x1) / 2;
	int cnt = 1;//记录尝试多少次
	double y = f(root);
	while (fabs(y) > EPS) {
		if ( f(root) > 0) 
			x2 = root;
		else 
			x1 = root;
		root = x1 + (x2 - x1) / 2;
		y = f(root);
		cnt++;
	}
	cout << "cnt=" << cnt << endl;
	printf("%.8f\n", root);
	return 0;
}

输出