二分算法笔记

二分

说起二分，大家应该都不陌生，第一次接触二分这个东西应该就是平常玩的一个猜数字的游戏，那么猜数字的话就是一个典型的二分查找的案例，也就是说我们可以从这个游戏中学习到什么呢？简而言之，就是每次去中点的一个操作，那么这个操作的优势在哪里呢，无非就是一个快速。那他为什么快呢？因为他每次可以排除一半的数字，范围每次可以根据我们所需要的进行调节。那么这个就是二分查找的运用了。在这之前。我们先说一下递推和递归。

递推

递推是一种用若干步可重复运算来描述复杂问题的方法。学过数学应该都知道数列吧。比如有名的斐波那契数列的递推公式就是
$$F\left(n\right)=F\left(n-1\right)+F\left(n-2\right)$$

分析一下，不难看出这么一长串的定义本质就是四个字：我为人人。观察，等号左边的 $F\left(n\right)$ 就是我，那么它可以分解成，右边前两项的和。那么自然而然地也可以知道递推算法的两个必要条件：

• 递推式
• 初始条件或边界条件

举个例子，要用递推求斐波那契数列就是先有式f[i]=f[i-1]+f[i-2]。然后定义初始化f[1]=1,f[2]=2。这两个东西结合起来就可以算出 $F\left(n\right)$ 了。

递归

递归的定义就非常简单了。也就是自己调用自己，也就是人人为我，跟分治其实非常类似。每一次都把问题分成跟原问题相比，具有结构相同，规模更小的特点，而且更为重要的是递归必须要有一个终点，或者称之为终止条件，不然无限制的递归下去会造成死循环的影响。然后通过小问题反推回大问题。比如搜索就是一种递归。

二分写法

首先，我们先说几个二分的注意事项：

1. 如果你要对这个数组查找，必须要保证数组完全有序，从小到大或从大到小，下面默认从大到小
2. 注意最后找到的下标，可能会挖坑。
3. 二分写法不同，下面仅展示个人写法。

同样地，这里我们也是分为两种思路写法，分别讲解。

递推写法

比较常见，时间和空间复杂度略低方便理解和阅读，思路写在注释里。

最后的输出就是分两种：$x$ 存在则返回首次出现的下标，不存在则返回大于 $x$ 的最小值下标（溢出可以通过判断 $x$ 是否超过最小值或者最大值避免）

int find(int x)//要查找的数 
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=l+(r-l)/2;//相比(l+r)/2的情况可以避免l+r越界
		if(x>a[mid])//如果小了，那么往前继续缩小范围
		{
			l=mid+1;
		}
		else//如果大了，往前找
		{
			r=mid-1;
		}
	}
	return l;//返回左端点
}

递归写法

时间和空间复杂度略高，比较少见

结果和递推一样，不多说了。

int find(int l, int r) 
{
	//递归边界
	if(l>r) 
	{
		return l;
	}
	int mid=l+(r-l)/2;//上面讲过，不再多说
	if(a[mid]>=x)//x是查找的数，思路类似，不多说了
		return find(l,mid-1);
	else
		return find(mid+1,r);
}