谈谈 二分查找

一、闲谈
二分查找，也叫拆半查找，我在这篇文章已经讲诉过查找的几种方法：数据结构之查找，这里就不再细讲。
这里要探讨以下几个问题：

1. 究竟什么时候我们要用while(left<=right),什么时候用while(left<right)?
2. 什么时候我们需要再while结束后才返回结果，即不在while内返回
3. 二分查找的一般步骤。

二、解答第一二问题
首先分清楚两者的差别，while(left<=right)，表示可以取到端点，而while(left<right)则不行。
所以，用while(left<=right)在while内返回结果，不存在则在while外面返回不存在
用while(left<right)在while外面判断并返回结果。
如果单纯是为找一个数，那么只需要while(left<=right),并在while内返回结果即可。
就目前看来，如果要while(left<right)，则需要在while外面判断是否能找到target，并返回
使用while(left<right)时需注意，二分时，必须一个端点包括mid，如 if(nums[mid]>=target) right=mid;
while(left<right)还有一个神奇的作用，它可以找到最小的符合条件的目标，因此，如果有多个满足条件的目标，欲得到最小的那个时，可采用while(left<right)
总之，二分查找时 建议使用while(left<right),不要使用while(left<=right)

三、解答第三个问题

二分查找的一般步骤：

1. 锁定查找范围，即确定left和right 的初始值
2. while(left<right) 、 求mid 、 获得conditions(查找的约束条件)
3. 由conditions来调整left和right
4. 返回查找结果
   例如：1011. 在 D 天内送达包裹的能力
   直接上代码：

   int shipWithinDays(vector<int>& weights, int D) {
        //二分查找
        //初步判断这个值应该落在，最大包裹重量和全部包裹重量之间
        int left=*max_element(weights.begin(),weights.end());
        int right=accumulate(weights.begin(),weights.end(),0);
        const int n=weights.size();
        while(left<right){
            int mid=left+((right-left)>>1);//suppose the result is mid
            int sum=0,need=1;
            //conditions
            for(int weight:weights){
                if(weight+sum>mid){
                    ++need; sum=0;
                }
                sum+=weight;
            }
            //check and adjust 
            if(need<=D) right=mid;//之所以取等是因为，要找到更小的result
            else left=mid+1;
        }
        return left;
    }