在编程中，查找是很重要的一环。

比方说，有一个一百万位的、单调递增的数组，需要你找到某个值在第几位；

比方说，有一个不规则函数，要你求出一个零点的位置；

等等等。

在这个时候，你总不能把这一百万都查找一遍吧？

这个时候

二分就派上用场了。

那么二分是什么呢？

你可以和同学做一个游戏，我们来模拟一下最基础的二分：

让你的同学在1-1000中随便抽取一个数字，然后让你猜

你每猜一个数字，让他告诉你，答案比这个数字大还是小；

那么，如果你每次都猜中间的数字，最多十次就可以猜出来答案了。

为什么呢？

因为2^10=1024>1000，2进制的10位最多能存储到1024的值，而1000在这里面。

你看，本来我们需要搜索1000次，现在10次就够了，这极大的优化了程序的时间复杂度。

我们来尝试一下最简单的二分算法：

//以下为情景1
//这里有一个写好的数组num[100000];
//我们要在这个数组里面查找6666这个数字的位置
//然后输出
int i = 0;//声明迭代器
int up = 100000;//声明上界
int down = 0;//声明下界
while(num[i] != 6666)
{
	int mid = (up + down)/2; //声明一个变量，用来存储上下界的中值
	if(num[mid] > 6666)up = mid;//如果num[mid]大于我们要找的6666，说明我们要找的6666的下标在mid之前，更新上界使其变为mid
    else down = mid;//否则在6666之后，更新下界
}

cout << i;

OK。

我们再来说一声二分法的变形。

比方说，现在有一个一元一次函数，

y=kx+b。

首先，函数已经给你了，

double func(doube x){
	return k * x + b;
}

然后我们再告诉你一个答案区间：

-1000到1000

以及答案精度：保留五位小数

下面来尝试一下：

//以下为情景2
//虽然一次函数你可以很简单的求出来kx+b=0的解，但是如果是三次函数呢？
//这里只是让你尝试一下方法
//来求kx+b=0的解
int i = 0;//声明迭代器
int up = 1000;//声明上界
int down = -1000;//声明下界
while(up-down<=0.00001)//循环条件为精度
{
	int mid = (up + down)/2; //声明一个变量，用来存储上下界的中值
	if(fucn(mid) * fucn(up) <= 0)down = mid;//根据零点存在性定理，如果func(mid) * func(up) <= 0，就说明答案在mid和up中间，那就更新down
    else up = mid;//否则更新up
}

cout << mid;//现在其实输出up、down、mid都可以，精度都满足

其实二分法还有很多很多的变种。

它的使用条件很简单：

只要这个东西是单调的，且有上下界，就可以用二分法来解决。

以后可能我们做的很多算法题都可以利用二分来提高运行速度。