本文主要是介绍二分法的专题总结——到底应该写小于还是小于等于、两个判断还是三个判断，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二分法的专题总结
二分法的本质是：寻找序列中第一个满足某条件的元素的位置。
二分法中通常让人迷惑的地方不外乎
（1）while中什么时候写小于等于，什么时候不写等于；
（2）while内部是写两个条件还是三个条件。
首先考虑升序排列的元素（降序等价），应当分为两种情况：（1）没有重复元素；（2）有重复元素。后者是前者的一般化，也就是说后者的算法也同样适用于前者。
（1）没有重复元素
这种情况下的问题一般是：查找某个元素target在序列中是否出现，如果出现则返回出现的序号，如果不出现，则返回-1。也就是确定一个区间[x,x]，target就是x位置的元素，如果没有这个元素，那么确定出来的区间是[x+1,x]，左边界大于右边界，也就是区间中不存在元素。
（2）有重复元素
这种情况下的问题则是，确定第一个大于等于target的元素序号，和第一个大于target的元素序号，两个子问题。
没有重复元素的二分查找代码如下：
int BinarySearch(const std::vector<int>& a, int target)
{int left = 0, right = a.size() - 1, mid;while (left <= right) {mid = left + (right - left) / 2;if (a[mid] == target)return mid;else if (a[mid] < target)left = mid + 1;elseright = mid - 1;}return -1;
}
上述代码中，需要注意的地方有三个：（1）while的条件是left==right；（2）while中是三个判断，并且其中一个判断是a[mid]<target，而不是a[mid]<=target；（3）right=a.size()-1而不是a.size()
对于（1）没有重复元素，所以当left>right的时候就代表了没有找到。这里是不重复元素这种特殊情况的写法。在下面的重复元素的例子中可以看到，这里其实也可以不这么写。
对于（2），三个判断也是不重复元素的特殊写法。因为找到了需要的值马上就返回了，所以有第一个if判断。在后面有重复元素的情况是没有第一个if判断的。有了第一个if判断，就把等于的情况分离出来了，所以是三个if else，对应等于、小于和大于。当第8行a[mid]<target条件判断成立时，说明target一定在mid点的右边（不包括mid），所以下面是把left收缩到mid+1；同样的道理，第10行else成立的时候，target一定在mid点的左边（也不包括mid点）（因为此时target<a[mid])，right收缩到mid-1.
对于（3），有两点原因：为了和（2）统一（也就是target在left和right点构成的闭区间中，而不是开区间中）所以应该a.size()-1；考虑a中的所有元素都小于target会发生什么：倒数第三轮循环的时候，end=a.size()-1,beg=a.size()，倒数第二轮循环end=a.size(),beg=a.size()，由于我们while的条件写的是beg<=end，所以此时仍然会进入循环计算mid，从而越界访问了a！！！在后面重复元素的情况中可以看到，由于我们的条件写的是beg<end，所以那里是写的right=a.size()
只要注意了上面三个点，元素不重复的二分查找很难写错。
有重复元素的二分查找代码如下：
（1）查找下界（第一个大于等于target的元素的序号，[x,y)的x）
int LowerBound(const std::vector<int>& a, int target)
{int left = 0, right = a.size(), mid;while (left < right) {mid = left + (right - left) / 2;if (a[mid] >= target) {// 中间的数大于等于target，往左子区间[left,mid]查找right = mid;}else {// 中间的数小于target，往右子区间[mid+1,right]查找left = mid + 1;}}// left==right，返回哪一个都可以return left;
}
（2）查找上界（第一个大于target的元素的序号，[x,y)的y）
int UpperBound(const std::vector<int>& a, int target)
{int left = 0, right = a.size(), mid;while (left < right) {mid = left + (right - left) / 2;if (a[mid] > target) {// 中间的数大于target，往左子区间[left,mid]查找right = mid;}else {// 中间的数小于等于target，往右子区间[mid+1,right]查找left = mid + 1;}}// left==right，返回哪一个都可以return left;
}
上面两个函数就确定了target的界。
LowerBound中，我们确定了第一个大于等于target的元素，UpperBound中，我们确定了第一个大于target的元素。
对于不重复的情况，就有：
target在nums中存在时：
nums[UpperBound(nums,target)]==target
并且有：
BinarySearch(nums,target)==UpperBound(nums,target)
target在nums中不存在时：
nums[UpperBound(nums,target)]!=target
所以说有重复元素的情况是没有重复元素情况的一般化。
上面的三段代码也说明了，有重复元素的二分更容易写在一个函数里面，而不是作为一个单独的函数（重复元素的二分只有一个return出口，而非重复元素的二分有两个），并且条件判断很容易，所以后面一种代码或许更加好用。（刷PAT得到的感觉）
为什么LowerBound中的a[mid]>=target时right=mid而a[mid]<target时left=mid+1和为什么UpperBound中的a[mid]>target时right=mid而a[mid]<=target时left=mid+1在注释中已经说得很清楚了。如果我们把LowerBound中的判断条件写成下面这样会怎么样呢？
if (a[mid] > target) {// 中间的数大于target，往左子区间[left,mid-1]查找right = mid - 1;
}
else {// 中间的数小于等于target，往右子区间[mid,right]查找left = mid;
}
乍一看很有道理，但是不要忘了我们LowerBound要解决的问题：寻找第一个大于等于target的元素。如果a中没有target的话，会返回离target最近的小于target的元素坐标，就把要寻找的目标值排除到搜索域外面了；如果a中有target，情况会更糟：死循环。考虑当a[right]=target，而a[left]<target，并且left=right-1的情况，此时mid的计算结果为left，而每次判断都会进入第二个分支，也就是left=left，永远不会跳出循环。UpperBound函数中也有类似的问题。
当a中的所有元素都小于target时，LowerBound和UpperBound的最终的结果都是left和right和a.size()三者相等，也就是得到了a中最后一个元素之后元素的位置。（这也就说明了为什么要初始化成right=a.size()）
当a中的所有元素都大于target的时候，LowerBound和UpperBound都返回0，此时第一个大于target的元素也就是a[0]。
有了上面对二分法和LowerBound和UpperBound的理解之后，就可以用stl中的的lower_bound函数和upper_bound函数了，CSDN上有介绍：关于lower_bound( )和upper_bound( )的常见用法
参考文献《算法笔记》第二版 胡凡
这篇关于二分法的专题总结——到底应该写小于还是小于等于、两个判断还是三个判断的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
