二分法最基础的实现就是猜数字游戏
猜数字游戏是令游戏机随机产生一个100以内的正整数，用户输入一个数对其进行猜测，需要你编写程序自动对其与随机产生的被猜数进行比较，并提示大了，还是小了，相等表示猜到了。如果猜到，则结束程序。
#include <iostream>
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 <cmath>
#include <iomanip>
#include <iostream>
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），是用来在一个有序数组中查找某一元素的算法。
二分查找的模板:
int binary_search(int start, int end, int key) {
int ret = -1; // 未搜索到数据返回-1下标
int mid;
while (start <= end) {
mid = start + ((end - start) >> 1); // 直接平均可能会溢出，所以用这个算法
if (arr[mid] < key)
start = mid + 1;
else if (arr[mid] > key)
end = mid - 1;
else { // 最后检测相等是因为多数搜索情况不是大于就是小于
ret = mid;
break;
}
}
return ret; // 单一出口
}
这里我们其实只需要理解就可以了，因为我们有STL:
C++ 标准库中实现了查找首个不小于给定值的元素的函数std::lower_bound和查找首个大于给定值的元素的函数std::upper_bound，二者均定义于头文件<algorithm>中。二者均采用二分实现，所以调用前必须保证元素有序。
这里就不再过多赘述了，大家可以自己看[链接登录后可见]
下面，我们来学习二分答案
如果答案具有单调性且有范围，那么就可以二分枚举答案，在答案合法的条件下不断逼近最优（如最大值最小或最小值最大），最后一个合法的答案就是最优解，这便是二分答案
二分答案模板:
//求最小值
int binary(int left, int right) {
int mid;
while(left < right) {
mid = (right + left) / 2;
if (check(mid)) right = mid;
else left = mid + 1;
}
return left;
}
//求最大值
int binary(int left, int right) {
int mid;
while(left < right) {
mid = (right + left + 1) / 2;
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}
我们先来看这道题:[链接登录后可见]
这道题是一道二分答案的板子题，当然也可以直接枚举，但是这种朴素算法肯定拿不到满分，大家可以用二分答案试着做一下
这里给出[链接登录后可见]
别忘了练习，任何算法只听懂是没有用的，这里帮大家整理了一个[链接登录后可见]
