剑指 Offer II 二分查找

068. 查找插入位置

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int l=0,r=nums.size();
        nums.push_back(1000000);//一定有数比target大 它在的位置会是最后一个插入的位置 可以直接return l
        while(l>1;
            if(nums[mid]>=target)r=mid;
            else l=mid+1;
        }
        return l;

    }
};

069. 山峰数组的顶部

山峰符合两段性

class Solution {
public:
    int peakIndexInMountainArray(vector& a) {
         int l=1,r=a.size()-2;
         while(l>1;
             if(a[mid]>a[mid-1])l=mid;
             else r=mid-1;//说明答案严格在左侧

         }
         return l;
    }
};

070. 排序数组中只出现一次的数字

class Solution {
public:
    int singleNonDuplicate(vector& nums) {
       /*
       二分的性质是 两两看成一组

       target左边 数都相同 
             右边 数都不同


       */
       nums.push_back(nums.back()+1);
       int l=0,r=nums.size()/2-1;//组数
       while(l>1;
           if(nums[mid*2]==nums[mid*2+1])l=mid+1;//在左边
           else r=mid;
       }
        return nums[2*l];//第l组第一个数
    }
};

071. 按权重生成随机数

class Solution {
public:
/*
二分查前缀和 下标
*/
   vectors;
    Solution(vector& w) {
        s=w;
        for(int i=1;i

class Solution {
public:
    int mySqrt(int x) {
       int l=0,r=x;
       //第一个y^2<=x
       while(l>1; //LL类型的1
           if(mid<=x/mid)l=mid;
           else r=mid-1;
       }
       return l;
    }
};

class Solution {
public:
    int minEatingSpeed(vector& piles, int h) {
        int l=1,r=1;
        for(auto x:piles)r=max(r,x);

        while(l>1;
            int time=0;
            for(auto x:piles)time+=(x+mid-1)/mid;
            if(time<=h)r=mid;
            else l=mid+1;

        }
        return l;
    }
};