6.1 704. 二分查找

  1. //第一种；
  2. class Solution {
  3. public:
  4.     int search(vector<int>& nums, int target) {
  5.         int left=0;
  6.         int right=nums.size()-1; //定义target在左闭右闭的区间里，[left, right]
  7.         while(left<=right){  //// 当left==right，区间[left, right]依然有效，所以用 <=
  8.             int middle=left+(right-left)/2;   // 防止溢出
  9.             if(nums[middle]==target){
  10.                 return middle;
  11.             }else if(nums[middle]<target){
  12.                 left=middle+1;
  13.             }else if(nums[middle]>target){
  14.                 right=middle-1;
  15.             }
  16.         }
  17.         return -1;
  18.     }
  19. };
  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         int left=0;
  5.         int right=nums.size(); //[left,right)
  6.         while(left<right){
  7.             int middle=left+(right-left)/2;
  8.             if(nums[middle]==target){
  9.                 return middle;
  10.             }else if(nums[middle]<target){
  11.                 left=middle+1;
  12.             }else if(nums[middle]>target){
  13.                 right=middle;
  14.             }
  15.         }
  16.         return -1;
  17.     }
  18. };

6.2 35. 搜索插入位置

//第一种
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){    //[left,right]
            int middle=left+(right-left)/2;
            if(target==nums[middle]){
                return middle;   
            }else if(nums[middle]<target){  //左区间 [left,middle-1]
                left=middle+1;
            }else if(nums[middle]>target){  //右区间 [middle+1,right]
                right=middle-1;
            }
        }
        return right+1;
    }
};

//第2种
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size();
        while(left<right){    //[left,right）
            int middle=left+(right-left)/2;
            if(target==nums[middle]){
                return middle;   
            }else if(nums[middle]<target){  //左区间 [left,middle-1）
                left=middle+1;
            }else if(nums[middle]>target){  //右区间 [middle+1,right）
                right=middle;
            }
        }
        return right;
    }
};

6.3 34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder=getLeftBorder(nums,target);
        int rightBorder=getRightBorder(nums,target);
        if(leftBorder==-2||rightBorder==-2){
            return {-1,-1};
        }
        if(rightBorder-leftBorder>1){
            return {leftBorder+1,rightBorder-1};   //注意下标
        }
        return {-1,-1};        
    }
    //分别寻找左右边界
    //寻找左边界
    int getLeftBorder(vector<int>& nums, int target){
        int left=0,right=nums.size()-1;
        int leftBorder=-2;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(nums[middle]>=target){   //锁定左边边界，不断向左收缩
                right=middle-1;
                leftBorder=right;
            }else{
                left=middle+1;
            }
        }
        return leftBorder;
    }
    //寻找右边界
    int getRightBorder(vector<int>& nums, int target){
        int left=0,right=nums.size()-1;
        int rightBorder=-2;
        while(left<=right){
            int middle=left+(right-left)/2;
            if(nums[middle]>target){  
                right=middle-1;
            }else{  //锁定右边边界，不断向右收缩, nums[middle] == target的时候更新left
                left=middle+1;
                rightBorder=left;
            }
        }
        return rightBorder;
    }
};

6.4 69. x 的平方根

class Solution {
public:
    int mySqrt(int x) {
        int left=1,right=(x>>1)+1;
        while(left<=right){
            int middle=left+((right-left)>>1);
            if(middle<x/middle){
                left=middle+1;
            }else if(middle>x/middle){
                right=middle-1;
            }else{
                return middle;
            }
        }
        return right;
    }
};

6.5 367. 有效的完全平方数

class Solution {
public:
    bool isPerfectSquare(int num) {
        int left=1,right=(num>>1)+1;
        while(left<=right){
            long long middle=left+((right-left)>>1);
            long long sum=middle*middle;  //有可能溢出，要用长整型来存储
            if(sum<num){
                left=middle+1;
            }else if(sum>num){
                right=middle-1;
            }else{
                return true;
            }
        }
        return false;
    }
};

6.6 875. 爱吃香蕉的珂珂

class Solution {
public:
    //计算速度为x时能吃完的时间
    int calTime(vector<int>& piles, int x){
        int hours=0;
        for(int i=0;i<piles.size();i++){
            hours += piles[i] / x;
            if(piles[i]%x>0){
                hours++;  //有剩余的，hour+1
            }
        }
        return hours;
    }
    int findMax(vector<int>& piles){
        int m_max=piles[0];
        for(int i=1;i<piles.size();i++){
            if(m_max<piles[i]){
                m_max=piles[i];
            }
        }
        return m_max;
    }
    //找左界
    int minEatingSpeed(vector<int>& piles, int h) {
        int left=1,right=findMax(piles)+1;
        while(left<right){
            int middle=left+(right-left)/2;
            if(calTime(piles,middle)<=h){  //能吃完，速度小一些
                right=middle;
            }else if(calTime(piles,middle)>h){ //不能吃完，速度大一些
                left=middle+1;
            }
        }
        return left;
    }
};

6.7 1011. 在 D 天内送达包裹的能力

class Solution {
public:
    //计算运载能力为x时，需要多少天运完
    int getDays(vector<int>& weights, int x){
        int days=0;
        for(int i=0;i<weights.size();){
            int temp=x;
            //不一定能装满，装不满时，要往后边继续装
            while(i<weights.size()){
                if(weights[i]>temp){
                    break;
                }else{
                    temp-=weights[i];
                }
                i++;
            }
            days++;
        }
        return days;
    }
    //找左边界
    int shipWithinDays(vector<int>& weights, int days) {
        //left为最小载重，货物的最大值，right为最大载重，即全部货物一次运完
        int left=0,right=1;
        for(int i=0;i<weights.size();i++){
            left=max(left,weights[i]);
            right+=weights[i];
        }
        while(left<right){
            int middle=left+(right-left)/2;
            if(getDays(weights,middle)<=days){
                right=middle;
            }else{
                left=middle+1;
            }
        }
        return left;
    }
};