DAY22 - 二分搜寻(一)

二分搜寻有随机访问的特性，在数组是有序的情况下，透过访问的元素，推测左右两侧的性质，展现较高的效率。
以下整理己主以下整理几种解题时会出现的模板

模板

标准的二分搜寻

//标准的二分搜寻
int find_target(const int& target, const vector<int>& arr){
    int f = 0;
    int b = arr.size()-1;
    while(b>=f){
        int mid = (b+f)/2; //中点
        if(arr[mid]==target){
            return mid;
        }
        if(arr[mid]>target){    //目前的mid>target，要寻找的值应该在左侧
            b = mid-1;  //已经确定mid不是target, 可以从mid-1移动b
        }
        if(arr[mid]<target){    //要寻找的值应该在右侧
            f = mid+1;  //已经确定mid不是target, 可以从mid+1移动f
        }
    }
    return -1;  //not found
}

如果没有搜寻到，两个指针的情形

//应对没有搜寻到目标，返回比目标大的值其索引

int find_target_return_f(const int& target, const vector<int>& arr){
    int f = 0;
    int b = arr.size()-1;
    while(b>=f){
        int mid = (b+f)/2; 
        if(arr[mid]==target){
            return mid;
        }
        if(arr[mid]>target){
            b = mid-1; 
        }
        if(arr[mid]<target){
            f = mid+1;
        }
    }
    return f;   //not found
    //return b;  // -->返回比目标小的值其索引
}

另一种写法

//返回较大索引的另一种写法
int find_target_return_bigger(const int& target, const vector<int>& arr){
    int f = 0;
    int b = arr.size()-1;
    while(b>f){ //这边要改写成没有等号，以免会无限循环(b==f时)
        int mid = (b+f)/2;  //中点
        if(arr[mid]==target){
            return mid;
        }
        if(arr[mid]>target){ //因目的是返回比目标大的最小索引，此处mid可能是答案，保留，寻找更小的索引
            b = mid;
        }
        if(arr[mid]<target){
            f = mid+1; //若小於target不符合规定，f不可能是答案，直接移动至mid+1
        }
    }
    return b;
}

有了模板之後就可以开始刷题了

例题实战

1482. 制作 m 束花所需的最少天数
编写achievable检查後，以二分搜寻法带入
((暴力法一一带入；速度太慢))

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
    //[暴力法]超时
        // vector<int> hash = bloomDay;
        // sort(hash.begin(), hash.end());
        // int res = -1;
        // for(int i = 0; i<hash.size(); i++){
        //     res = hash[i];
        //     int cnt = 0;
        //     int contin = 0;
        //     for(int j = 0; j<bloomDay.size(); j++){
        //         if(bloomDay[j]<=res){
        //             contin++;
        //             if(contin==k){
        //                 cnt++;
        //                 contin = 0;
        //             }
        //         }
        //         else{
        //             contin = 0;
        //         }
        //         if(cnt==m){
        //             return res;
        //         }
        //     }
        // }
        // return -1;
    //[二分搜寻法]优化通过
        int mmax = -1;
        for(int i = 0; i<bloomDay.size(); i++){
            mmax = max(bloomDay[i], mmax);
        }
        int res = -1;
        int b = mmax;
        int f = 0;
        while(b>=f){
            int mid = (f+b)/2;
            if(achievable(bloomDay, m, k, mid)){
                res = mid;
                b = mid-1;
            }
            else{
                f = mid+1;
            }
        }
        return res;
    }
    bool achievable(vector<int>& bloomDay, int m, int k, int day){
        int cnt = 0;
        int contin = 0;
        for(int i = 0; i<bloomDay.size(); i++){
            if(bloomDay[i]<=day){
                contin++;

-----


                if(contin==k){
                    cnt++;
                    contin = 0;
                }
            }
            else{
                contin = 0;
            }
            if(cnt==m){
                return true;
            }
        }
        return false;
    }

};

这题之前有放过了，再提一次==刷了两次还是会没想法
162. 寻找峰值

if nums[mid]>nums[mid+1] 则 [mid+1 ~ N]必有峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int f = 0;
        int b = nums.size()-1;
        int mid = -1;
        while(b>f){
            mid = (f+b)/2;
            if(nums[mid]>nums[mid+1]){
                b = mid;
            }
            else{
                f = mid+1;
            }
        }
        return f; 
    }
};