基础算法（二）二分

整数二分

二分查找这个概念很多人应该都知道，但许多初学者经常遇到的一个误区就是，他们觉得只有当一个数组有序的时候才能用二分，其实这是不对的。

基本思想

二分分的是某个性质，只要这个数组满足能够一分为二，左边满足这个性质，右边不满足这个性质，那么我们就可以通过二分查找到这个性质的边界，这才是二分的本质，我们可以找边界上满足这个性质的，也可以找边界上不满足这个性质的，由此我们有两种情况，下面分别来说。

实现方法

第一种情况，对一个数组Q，左右两端记为l和r，当我们要找边界上满足这个性质的数的时候，我们先有中间数mid，之后我们判断q[mid]是否满足这个性质，如果满足，则将区间缩小至[ mid , r ]，否则将区间缩小至[ l , mid-1 ]，这样重复下去，直至区间中只剩一个数，这个数就是我们要找的边界上满足这个性质的数。

第二种情况，当我们要找边界上不满足这个性质的数时，一样地，我们判断q[mid]是否满足这个性质，如果满足，则将区间缩小至[mid+1 , r]，否则将区间缩小至[ l , mid ]。

在刚刚接触这个的时候，很多人都觉得这个有点抽象，不好理解，不知道这个区间为什么是这样变的，我说说我的理解，首先最重要的一点，我们需要保证区间内我们要找的点是始终存在的，拿第一种情况举例，我们要找的点是满足这个性质的，所以当mid也满足这个性质时，我们可以说mid应该包含在之后的区间里，因为在极端情况下，mid完全有可能就是我们要找的这个点，反之，当我们已经知道mid不满足这个性质，那我们就能说，我们要找的点肯定不是mid，这时我们划分区间时就应该把mid去掉，其次，我们应该尽量使区间端点有着不同的性质，因为我们找的是边界点，如果区间内所有的点都满足这个性质，那么还谈何边界呢？当我们清楚这两点后，接下来的代码实现就不难了。

代码模板

#include <iostream>

using namespace std;

//当区间划分为[mid+1 , r]和[l , mid]时
int b_search1(int l, int r)
{
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	return l;
}

//当区间划分为[mid , r]和[l , mid-1]时
int b_search2(int l, int r)
{
	while (l < r)
	{
		int mid = l + r + 1 >> 1; //这里要注意当l=mid时要让mid = l + r + 1 >> 1
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}

浮点数二分

和整数二分不同，浮点数二分我们不需要去考虑边界问题，这就使得浮点数二分的实现简单了许多。基本思想与整数二分一致，我们下面讲讲它的实现方法。

实现方法

由于是浮点数，我们每次二分时能严格地将区间一分为二，与整数二分一样的，我们每次选取区间时要满足两个条件，即保证区间内我们要找的点是始终存在的，同时尽量使区间端点有着不同的性质，而与整数二分不同的是它的结束条件，当两个区间端点的距离足够近时，我们就可以结束循环，将r或者l当作我们的答案。