你真的理解二分的写法吗？
（给算法爱好者加星标，修炼编程内功）
来源：FlushHip
blog.csdn.net/FlushHip/article/details/79261608
说实话，我之前也不完全理解二分查找的各种写法，导致在写各种二分的边界时我总是弄不清边界值，于是我只能通过暴力枚举这些边界值，去一个一个试，这样子效率真的很低下。于是，痛定思痛，一定要把二分的写法吃透，就有了这篇文章。
二分写法的种类
二分写法的种类很多，最常见的就是二分查找了的最普遍写法了。代码如下：
bool bFind(int a[], int left, int right, int tag)
{
for (; left <= right; ) {
int mid = (left + right) >> 1;
if (a[mid] == tag)
return true;
else
a[mid] < tag ? l = mid + 1 : r = mid - 1;
}
return false;
}
正如我刚才说的，这只是最普通的二分，实际上，二分还可以实现非等值查找，例如平时所说的二分求上界，二分求下界之类的。
下面我用乘法原理来告诉你们二分查找有多少种写法。
区间的开闭 - [开区间还是闭区间] 左右端点 - [这个端点是和上面区间开闭联系的，具体表现为左开还是左闭，右开还是右闭] 中点是取整还是进一 - [在计算中点的时候到底是 (left + right) >> 1还是(left + right + 1) >> 1]大于还是小于 - [这个对应上下界问题] 取不取等于 - [是大于等于还是小于等于] 第一个还是最后一个 - [找第一个大于目标的位置还是找最后一个大于目标的位置]
每个选项都是两种可能，于是二分写法一共有 26=64 2 6 = 64 2^6=64种写法。也就是说，从这六个选项中的每个选项中任意挑选一个就可以组成一个二分的问题。
那么这么多种类的二分，是不是每种二分都要去记呢？肯定不要啊，不然我还写这博客干嘛。接下来我会告诉你一个通用的方法。
先看一个题目吧，有题目才有切入点。
题目背景
统计一个数字在升序数组中出现的次数。
题目解析
做法参见
剑指Offer66题之每日6题 - 第七天(http://blog.csdn.net/flushhip/article/details/79052383)中的第一题。
代码
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int pre, last, l, r;
// 下界
for (l = 0, r = data.size() ;l < r; ) {
int mid = (l + r) / 2;
if (data[mid] >= k)
r = mid;
else
l = mid + 1;
}
pre = r;
// 上界
for (l = -1, r = (int)data.size() - 1; l < r; ) {
int mid = (l + r + 1) / 2;
if (data[mid] <= k)
l = mid;
else
r = mid - 1;
}
last = l;
return last - pre + 1;
}
};
详解
这个题目里，要用一个二分去求下界，一个二分求上界。
求下界
下界的定义是什么，就是找到一个数，这个数是第一个大于等于k的数，这个数的位置就是下界；
注意到二分的边界我设成了l = 0, r = data.size()，这是一个左闭右开的区间，中点处我用的是mid = (l + r) / 2，二分结束后，l等于r；
下界的位置靠近左端点，所以我们从左端点开始找，因此，可以看到，二分中l的位置在一步一步向右端点靠近(因此要加一)，而r只是起到缩小范围的作用；
右端点是个开端点，这是为了处理有序数组中没有一个数字比k大的情况，因此，如果查找失败，l和r可以指向一个空的位置，也就是数组的最后一个位置的后一个位置，这个程序设计中的“左闭右开”区间的思想是一样的；
至于中点处为什么要向下取整，原因是这样的：如果这个题要你顺序查找这个有序数组找到下界，你会从哪里开始找？肯定是左边第一个元素开始找啊，你总不可能从第二个元素开始找吧，这就是为什么要向下取整的原因，向下取整可以避免漏掉最优解；
如果你还不明白，那么我举个例子你就知道了，数组为[-2], k = 3，l = 0, r = 1，然后你二分的时候中点向上进一，那么mid = (0 + 1 + 1) / 2 = 1，然后你会发现mid不在数组中，怎么可能啊，mid是区间的中点，那必然会在数组中啊！这就是求下界的时候为什么中间要向下取整了；
还有一点要始终记得，二分结束后，l = r，因此最后l, r都是答案。
求上界
刚刚讲了求下界，求上界也如法炮制。
求上界求的是最后一个大于等于k的数字的位置，我们把数组反过来，以右端点作为起点开始查找，这个时候第一个小于或等于k的元素的位置就是原问题的上界；
你把求上界转化成求下界来看，是不是代码中的一切东西都理所当然了；
r = data.size() \- 1, l = \-1，因为把数组反过来的，故右端点就是起点，结束的位置就是第一个元素前面的一个位置；
mid = (l + r + 1) / 2，因为把数组反过来了，因此这里的向上进一其实就是反过来之后的向下取整。
总结
可以看到，求上界可以转化为求下界来做，因此，这里详细总结一下求下界的做法。
求下界第一件事就是确定左右端点范围，由于求下界是求第一个满足condition条件的位置，这里用condition是为了把这个求下界的方法一般化，求第一个满足条件的位置，因此，以左端点为起点；
最后一个元素的后一个位置作为终点，这是为了在没有满足条件的解可以得到一个合理的值(指向最后一个元素的后一个位置就是代表着没有找到下界)；
中点取靠近起点的一端，根据靠近的位置选择向下取整还是向上进一；
在缩小范围的时候，如果mid满足条件，那么令r = mid, 这样子可以缩小范围([mid + 1, r)是一定不满足条件的，但mid有可能是答案，没关系，我们让l来等于mid就行，r只管缩小范围)，而且，这样可以保证一定有解；
如果mid不满足条件，就令l = mid + 1, 由于[l, mid]是一定不满足条件的，故让l一步步靠近r来找到满足条件的答案。
这样，无论是64种二分中的任何一种，你都可以按照这种求下界的方法来做了。
模板
class Solution {
public:
static bool cmp1(const int &a, const int &b) {
return a >= b;
}
static bool cmp2(const int &a, const int &b) {
return a <= b;
}
// 求下界
int getDown(vector<int> data, int k, bool (*cmp)(const int &, const int &))
{
int l, r;
for (l = 0, r = data.size() ; l < r; ) {
int mid = (l + r) / 2;
if (!cmp(data[mid], k))
l = mid + 1;
else
r = mid;
}
return l;
}
// 求上界
int getUp(vector<int> data, int k, bool (*cmp)(const int &, const int &))
{
int l, r;
for (l = -1, r = data.size() - 1; l < r; ) {
int mid = (l + r + 1) / 2;
if (!cmp(data[mid], k))
r = mid - 1;
else
l = mid;
}
return l;
}
int GetNumberOfK(vector<int> data ,int k) {
int up = getUp(data, k, cmp2), down = getDown(data, k, cmp1);
return up - down + 1;
// return getUp(data, k, &cmp) - getDown(data, k, &cmp) + 1;
};
这个模版以上面那个题目为背景写的，用了一个函数指针，这样可以把这个问题一般化，这个函数指针指向一个比较函数，这个比较函数中你就写合法的条件就可以了， STL中就是这么设计它们的lower_bound的。
其他
既然讲到了 STL，我就再告诉你upper_bound函数，lower_bound函数和我们上面说的求下界是一模一样的，但是，upper_bound就有点不一样了，它也是求上界，但是答案是上界的后一个位置；
利用我们刚才说的求下界，我们可以在此基础上改编一下求下界的方法，让它也能求上界，这样改编出来的函数就和upper_bound一样了，但是这样改编出来的函数只适合上面的这个题目背景，具体问题具体分析，这也是为什么 STL有了lower_bound为什么还要搞一个upper_bound的原因了；
求下界的函数主体不要动，只要改一下cmp2就好了。想一下，求最后一个大于等于k的元素的位置，那我们如果求得了第一个大于k的元素的位置，那么这个位置是不是就是答案的后一个位置，所以，cmp2中的内容改成return a > b;然后调用getDown(data, k, cmp2)就可以求得上界的后一个位置了。
- EOF -
觉得本文有帮助？请分享给更多人
推荐关注「算法爱好者」，修炼编程内功
点赞和在看就是最大的支持❤️