力扣刷题二分查找D3

思路：题目直接换成找到面积最大的区域即可。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int area=0;//面积大小
        int max_area=0;
        int left,right;
        int L=0,H=0;
        left=0;right=n-1;
        while(left<right){
            L=right-left;
            H=min(height[right],height[left]);
            area=L*H;
            max_area=max(max_area,area);
               
            if(H==height[left])
                left++;
            else right--;
            
            
        }
        return max_area;
    }
};

二分查找正文 

暴力遍历 0(n)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
        //请你找出给定目标值在数组中的开始位置和结束位置。
        //非递减顺序排列的整数数组 nums
        //暴力解法：遍历。
        int n=nums.size();
        int left=0,right=n-1;
        for(right;right>=0;right--){
            if(nums[right]==target)
                break;
        }
        for(left;left<n;left++){
            if(nums[left]==target)
                break;
        }
        if(left>right) return {-1,-1};
        return {left,right};
    }
};

题目要求0(lgn) 所以使用二分法。（当然，我觉得这个用二分纯粹是为了练手，实际操作上没有任何意义）

class Solution {
public:
    int mid_search(int target,vector<int>& nums){
        //找第一个大于等于target的
        int n=nums.size();
        int left=0,right=n-1;
        int mid=0;
        while(left<=right){
            mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }
            else //if(nums[mid]>=target)
                right=mid-1;            
        }
        return left;
    }
    int maximumCount(vector<int>& nums) {
       //给你一个按 非递减顺序 排列的数组 nums .
        //返回正整数数目和负整数数目中的最大值。
        //找到数字0的位置。
        //二分查找法找到数字0
        int n=nums.size();
        int i=mid_search(0,nums);//找到第一个大于等于0的位置。
        int j=mid_search(1,nums);//找到第一个大于等于1的位置。
        return max(i,n-j);
    }
};

思路：一开始想把相成的结果，存储到一个数组。然后二分查找

--》potions数组无序，先排序。拍一次就行，所以在循环外边

--》因为每一次potions数组×的是同一个数，所以把二分查找的targrt，修改为success/spill

class Solution {
public:
    int mid_search(vector<int >& nums,long long target){
        int n=nums.size();
        int left=0,right=n-1;
        int mid=0;
        while(left<=right){
            mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }
            else//> =
            right=mid-1;
        }
        return left;
    }
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
       //一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
        //大于等于 success 使用二分法。找到第一个大于等于的界限。返回 n-left
        vector<int> pairs;
        int n=potions.size();
        sort(potions.begin(),potions.end());
        for(int i=0;i<spells.size();i++){
            //vector<long long> sp;
            //for(int j=0;j<potions.size();j++){
                
                //sp.push_back(potions[j]*spells[i]);
            //}
           // long long target=(success-1)/spells[i];
            long long target = (success + spells[i] - 1) / spells[i];
            int pair=mid_search(potions,target);
            pairs.push_back(n-pair);
        }
        
        return pairs;
    }
};

 破题二心死了，半天没解决

代码为错误版本。

class Solution {
public:
    // 进行二分查找，找到最小的 nums[i] >= target 的索引位置
    int mid_search(vector<int>& nums,long long target){
        int n=nums.size();
        int left=0,right=n;
        int mid=0;
        while(left<right){
            mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }
            else right=mid;
        }
        return left;
    }
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        //长度为 n 的整数数组 nums  ，统计有几对，不需要返回下标，
        //先排序 
        //0 1 7 4 4 5--->0 1 4 4 5 7  3-6之间
        //第一层遍历i，用二分找到介于 l-i---r-i之间的值。
        //复杂度0(nlogn)
        sort(nums.begin(),nums.end());
        int n=nums.size();
        long long ans=0;
        for(int i=0;i<n;i++){
           int L= mid_search(nums,lower-nums[i]);
           int R=mid_search(nums,upper-nums[i]+1);
           ans+=R-L;
        }
        return ans/2;
    }
};

而在本题当中，每次累加的元素不应该从头开始。应该设置一个开头计算的位置。 

开头计算的位置可以设置为遍历元素的下一个。

自改代码如下： 

class Solution {
public:
    // 二分查找，寻找大于等于 target 的最小索引
    int search_mid(const vector<int>& nums, int target, int left, int right) {
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());  // 排序数组
        int n = nums.size();
        long long ans = 0;

        // 遍历每个元素 nums[i]，找到符合条件的 pair
        for (int i = 0; i < n; i++) {
            int num = nums[i];

            // 查找满足 lower <= num + nums[j] < upper 的区间
            // 左边界：num + nums[j] >= lower -> nums[j] >= lower - num
            int left = search_mid(nums, lower - num, i + 1, n);  // 查找 >= lower - num
            // 右边界：num + nums[j] < upper -> nums[j] < upper - num
            int right = search_mid(nums, upper - num+1, i + 1, n);  // 查找 < upper - num==> >=upper - num+1

            // 累加满足条件的对数
            ans += (right - left);
        }

        return ans;
    }
};

        //citations 已经按照 升序排列 
        //至少 有 h 篇论文分别被引用了至少 h 次
        //被引用次数c[i], 有n-i个文章引用至少c[i]次。
        //找到c[i]==n-i 的位置
        //对数时间复杂度 二分查找
        //二分 target 设为n-i
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1; // 设置正确的右边界
        
        while (left <= right) { // 继续查找直到左边界超过右边界
            int mid = left + (right - left) / 2;
            
            if (citations[mid] < n - mid) {
                // 如果 citations[mid] < n - mid，说明当前论文不足以形成 h-index，向右查找
                left = mid + 1;
            } else {
                // 否则，可能找到满足条件的位置，向左查找
                right = mid - 1;
            }
        }
        
        // 返回 h-index
        return n - left;
    }
};

875. 爱吃香蕉的珂珂 https://leetcode.cn/problems/koko-eating-bananas/

没读懂题，看了一下题解。就是猜数，猜到一个能满足条件的最小的数。

由于速度是一个整数，可以使用「二分查找」，经典的《幸运 52》猜价格游戏就是这样；
确定搜索的速度范围：最小是 1，最大是香蕉堆里最大的那一堆的香蕉个数；
速度越大，耗时越少，速度越少，耗时越大。
「二分查找」先猜一个速度（位于搜索范围中间），然后用这个速度去尝试耗时（需要遍历一次香蕉堆）：如果耗时严格大于 h，说明速度小了，应该猜一个更大的速度，所以搜索范围是 [mid + 1..right]，设置 left = mid + 1 。反之，耗时小于等于 h，说明当前猜的这个速度 mid 可能是符合题意的一个解（不能排除掉，后面的搜索表示找有没有更小的速度），所以搜索范围是 [left..mid]，设置 right = mid。

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        //第 i 堆中有 piles[i] 根香蕉。
        //先排序
        sort(piles.begin(),piles.end());
        int n=piles.size();
        if(n==h) return piles[n-1];
        //这个v，需要满足条件
        //v要尽可能的小。-----》 珂珂喜欢慢慢吃。
        //h 要刚刚好    但仍然想在警卫回来前吃掉所有的香蕉。
        //sum(pile[i]/v)==h
        
        int left=1,right=piles[n-1];
        while(left<right){
            int  sum_h=0;
            int v=left+(right-left)/2;
            /*for(int i=0;i<n;i++){
                if(piles[i]%v) 
                sum_h+=(piles[i]/v)+1;
                else sum_h+=(piles[i]/v);
                } */
            for (int pile : piles) {
            sum_h += (pile + v - 1) / v;  // 等效于 ceil(pile / mid)
            }
            if(sum_h>h)
                left=v+1;
            else right=v;
        }
        return right;
    }
};