二分详解

前言

二分是一种简单且应用广泛的算法思想。但落实到具体问题的解决上，还是有些东西值得细说的，现在让我们来掰扯掰扯~~

概览

引入

三分支版二分

首先，我们来看看这么一个问题：

给定一个 按照升序 排列且 无重复元素 长度为 $n$ 的整数数组，以及 $q$ 个查询。
对于每个查询，返回一个元素 $k$ 的位置（位置从 $0$ 开始计数)。
如果没有找到的话输出 $-1$ 。

对于这么一个在序列里查找某个值的问题，最简单粗暴的方式就是把数组遍历一次，看看有没有元素和 $k$ 相等。这么做的话，一次查询的时间复杂度是 $O(k)$ 的，如果查找 $n$ 次， $n$ 和 $k$ 是同一个数量级，且都非常大（算它都是 $10^9$ 量级好了）。那么总的复杂度就是 $O(n^2)$ 的，在查询操作密集的场景里，这种方式显示时不能被我们所接受的。

而在有序的条件下，其实我们不需要从头到尾的遍历查询。

如上图有一个升序排列的数组： $1,3,5,6,7,11,13,15,17,20$ ，需要在这个序列中查找 元素 $k=3$ 的下标，我们就可以从中间开始找。

首先，我们用两个指针 $L$，$R$ 分别指向数组的首和尾，令 $mid=（L+R）/2$ ，

这样就可以把一个数组分成两半，接下来我们只需要不断循环判断我们所要寻找的 $k$ 是在$a[mid]$ 这个位置，还是左边的区间 $[L,mid-1]$ 里，亦或是 $[mid+1,R]$ 即可。

代码

1
2
3
4
5
6
7
8
9
10
11

int search(int *a,int k){
    int l = 0,r = n-1;
	while(l<=r){
        int mid = (l+r)/2;
        if( a[mid] == k )retun mid;
        else if(a[mid]>k) r = mid-1;
        else l = mid+1;
    }
    return -1;	//如果没有找到返回-1
}

有朋友可能会问，这思想和代码都很简单，有啥好细抠的？莫急嘛，我们再来仔细看下题目，可以发现这题的相对来说是非常理想的——没有重复元素！！！

所以，当序列出现多个相同的答案时，这个算法只能找到它第一个找到的位置。但当出现多个相同答案的时候，我们往往需要的是求出这些相同答案的下标的上下界。

对于这个需求，上面这种简单的三分支形式的二分写法显然是不能完成的，这就是我们要讨论的重点、难点。

两分支版二分

既然三分支版本存在这样的问题，那我们不用三分支，直接用 if-else 这种两分支的形式可不可以解决这个问题？这里先给出结论：可以。但需要注意很多细节。

如上图：

• mid这个指针该是处于红框中，还是绿框中呢？
• 处在这两个框中的区别是什么？

带着这些问题，我们先直接来看代码模板，再来剖析原理：

左边界版

代码

1
2
3
4
5
6
7
8
9

int Lower_bound(int k){
    int l  = 0,r = n-1;
    while(l<r){
        int mid = (l+r)/2;
        if(a[mid]>=k)r = mid;
        else l = mid+1;
    }
	a[l]==k?return l:return -1;
}

右边界版

代码

1
2
3
4
5
6
7
8
9

int Upper_bound(int k){
    int l = 0,r = n-1;
    while(l<r){
        int mid = (l+r+1)/2;
        if(a[mid]<=k)mid = l;
        else r = mid-1;
    }
    a[l]==k?return l:return -1;
}

看完代码后，你可能问号更多了。

1. 为什么 while 循环条件中 $l≤r$ 变成小于了？
2. 为什么中间值 mid 左边界版是 $(l+r)/2$ ，而右边界版是 $(l+r+1)/2$ ？
3. 里面的条件判断结束后，一下是 $mid = l$ ，一下又是 $mid=r$，这怎么记？

这一切的问题，再看完下面的演示过程后都能迎刃而解。

过程演示

以在 $1,3,3,3,5,7,9,11,13,15,15$ 序列中寻找 $k=3$ 的下标下界为例：

第 1 次循环：

这时，$ a[mid]=7 ≥ 3$ ，令右边界指针 $r = mid$ 。

第 2 次循环：

$ a[mid]=3 ≥ 3$ ，令右边界指针 $r = mid$ 。

第 3 次循环：

$ a[mid]=3 ≥ 3$ ，令右边界指针 $r = mid$ 。

第 4 次循环：

终于 $ a[mid]=1 ≤ 3$ ，且 $mid$ 在 $l$ 所处的位置，所以令左边界指针 $l = mid+1$ 。

至此 $ l<r$ 的循环条件不成立，我们想要的答案就在 $a[l]$ 或者 $a[r]$ 的位置上。当然，如果数组里本来就没有所查找的值， $l$ 和 $r$ 也是会相等而退出循环的。

所以最后我们要加一句判断：

1

a[l]==k?return l:return -1;//如果没找到，就返回-1

小结

当我们

例题

1、数的范围