二分法看似很简单，但是很容易出错，还有较多的变式
二分法不仅是一种技巧，更是一种快速检索的思想，不要局限于套模版
二分的本质并不是单调性，如果有单调性一定能二分，但是即使没有单调性也有可能应用二分解决问题
二分法最常见的应用场景是在有序序列中快速查找，但是这儿的有序可以拓展到更宽泛的概念上，只要一个序列能按照某个确定的性质分为两部分，就很可能有二分法发挥作用的空间
总结二分思路：
1）始终取闭区间，check时用<=或>=
2)不要尝试记忆check结果和之后的区间变换的对应关系，而是在脑子里面模拟判断一下下一步的区间往哪边取
3）下一步处理的时候，总是选择答案所在的区间进行处理
4）取下一步的区间的时候，注意一个细节：left = mid + 1对应的mid = left + right >> 1; 而right = mid - 1对应的mid = left + right + 1 >>1
举个例子，剑指offer上的“旋转数组的最小数字”这道题
描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为 0，请返回 −1。
二分解法：
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
if(!n) return -1;
if(nums[n - 1] > nums[0]) return nums[0];
int l = 0, r = n - 1;
while(r >= 0 && nums[r] == nums[0]) r --;
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};
这道题可以以nums[0]的大小为界将数组分为两部分，以这个性质作为二分法的条件，找到目标元素
不能死套模版，要具体情况具体分析，上面这道题边界条件的判断方法与下面的三个模版都不一样，还有其他可能情况，比如找“比目标元素小的最大一个元素”，或者找“最后一个等于目标值的元素”，都可以用二分法做，但是不可能记住所有情况下的边界判断方法
1. 一般情况
推荐yxc的模版 二分查找算法模板
套用上面的模版，有几个关注点：
- 循环结束的条件是
l < r,循环结束的时候一定有l == r - 为了防止出现死循环，中点
mid分别有两种取法：r = mid时，mid == l + r >> 1;l = mid时，mid = l + r + 1 >> 1 l和r哪个取mid需要根据实际问题情景分析确定- 这种一般情况的二分法，循环结束后
l == r,二者都在我们寻找的中点位置
2. lower_bound 和upper_bound
二分法最常见常用的变式是求上下边界
lower_bound指返回第一个“大于等于value"的元素位置（可插入”元素值为 value“且 ”不破坏有序性“的 第一个 位置）
upper_bound指返回第一个“大于value”的位置（可插入”元素值为 value“且 ”不破坏有序性“的 最后一个 位置）
- upper_bound - lower_bound = 数组中 value 的个数
lower_bound实现
不断二分，右边界（last）找到大于等于key值的最左边的位置，用左边界（first）不断向右边界逼近
int mylower_bound(int* array ,int size,int key){
int first = 0, middle ,last = size-1;
while(first<last){
middle = (first+last) >> 1;
if(array[middle] <key ) //当middle小于要找的位置 ， first +1 也不会超过key的位置，最多相同
first = middle + 1;
else
last = middle ; //middle有可能等于要找的位置 ， last = middle ， 用first不断逼近
}
return first;
}
upper_bound实现
不断二分，右边界（last）找到最靠左的比key值大的位置，用左边界（first）不断向右边界逼近
int myupper_bound(int* array ,int size,int key){
int first = 0, middle ,last = size-1;
while(first<last){
middle = (first+last) >> 1;
if(array[middle] <= key ) //此时要找的位置一定在mid右边，用first不断逼近
first = middle + 1 ;
else
last = middle; //要找的位置可能取在middle处
}
return first;
}
顺便学习感受下stl源码
//lower_bound
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = distance(first,last);
while (count>0)
{
it = first; step=count/2; advance (it,step);
if (*it<val) { // or: if (comp(*it,val)), for version (2)
first=++it;
count-=step+1;
}
else count=step;
}
return first;
}
//upper_bound
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
ForwardIterator it;
iterator_traits<ForwardIterator>::difference_type count, step;
count = std::distance(first,last);
while (count>0)
{
it = first; step=count/2; std::advance (it,step);
if (!(val<*it)) // or: if (!comp(val,*it)), for version (2)
{ first=++it; count-=step+1; }
else count=step;
}
return first;
}
浮点数二分
因为不需要考虑下取整的问题，所以好处理
模板题目