二分算法~

二分法最基础的实现就是猜数字游戏

猜数字游戏是令游戏机随机产生一个100以内的正整数，用户输入一个数对其进行猜测，需要你编写程序自动对其与随机产生的被猜数进行比较，并提示大了，还是小了，相等表示猜到了。如果猜到，则结束程序。

#include 
using namespace std;
int main() {
// 输入要猜的数字
	int k;
	cin >> k;
// 定义下限，初始化为1
	int start = 1;
// 定义上限，初始化为100
	int end = 100;
// 定义中点
	int mid;
// 记录猜了多少次
	int cnt = 0;
// 执行循环，不断的猜数字
	while (start <= end) {
		// 猜start和mid的中点
		mid = (start + end) / 2;
		// 每猜一次，次数加1
		cnt++;
		// 输出调试信息
		cout << "[" << start << "," << end << "] " << mid << endl;
		// 比较k和mid的大小
		// 相等，猜中了！
		if (mid == k) break;
		// 猜的数字太大，将范围调整成[start,mid-1]
		else if (k < mid) end = mid - 1;
		// 猜的数字太小，将范围调整成[mid+1,end]
		else start = mid + 1;
	}
	// 输出结果
	cout << cnt << endl;
	return 0;
}

通过对猜数字游戏代码的理解我们可以发现二分法的本质:

以在一个升序数组中查找一个数为例。(在猜数字当中就是1-100),它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

通过上面的学习，我们可以来做一道题:

给定一个浮点数k，1<=k<=105，请输出k的平方根x，使得x*x与k的误差不超过0.001

这道题可以使用C++STL中的sqrt来实现，但是我们这里使用二分法，代码实现:

#include 
#include 
#include 
using namespace std;
// 误差临界值
const double diff = 0.001;
int main() {
	// 输入要猜的数字，注意是小数
	double k;
	cin >> k;
	// 定义下限，初始化为1
	double start = 1;
	// 定义上限，初始化为k
	double end = k;
	// 定义中点x，表示要猜的根号
	double x;
	// 记录当前误差
	double d;
	// 重复执行猜根号的过程
	while (start <= end) {
		// 猜start和mid的中点
		x = (start + end) / 2;
		// 计算当前误差
		d = fabs(x * x - k);
		//输出调试信息
		cout << start << ", " << end << ", ";
		cout << x << "," << x*x << endl;
		// 比较k和x*x的大小
		// 误差小于等于diff，结束循环
		if (d <= diff) break;
		// 猜的数字太大，将范围调整成[start,x]
		else if (k < x * x) end = x;
		// 猜的数字太小，将范围调整成[x,end]
		else start = x;
	}
	// 保留3位有效数字，并输出结果
	cout << fixed << setprecision(3) << x << endl;
	return 0;
}

接下来，我们开始正式学习二分查找

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是用来在一个有序数组中查找某一元素的算法。

 二分查找的经典题目:

给定一个升序数组，包含N个数字，再给定一个数字t，请输出t在数组中的下标，若t不在数组中输出-1。

to be continued