【LeetCode - 二分】

1. 注意索引区间，是的[ )，还是[ ]
2. 左边界 速度越小越好，right = mid [left mid] ~ [mid 1 right]
3. 右边界 容纳的人越多越好。 left = mid [left mid - 1] ~ [mid right]

二分模板 注意相等的变量赋值 mid需要加1的情况 右边界减1

int leftBound(vector<int>& nums, int target) { 
                int left = 0;         int right = nums.size(); // 取数组长度，然后while循环left取不到num.size(), 所以while中是 <         // 找左边界         while (left < right) { 
                    int mid = left   (right - left) / 2;             if (nums[mid] > target) { 
                        right = mid;             } else if (nums[mid] < target) { 
                        left = mid   1; // left必须是mid 1.因为遍历的范围是[left, right) 获取到mid后区间分为[left, mid) [mid 1, right)             } else if (nums[mid] == target) { 
                        right = mid;             }         }          return left;     }      int rightBound(vector<int>& nums, int target) { 
                int left = 0;         int right = nums.size(); // 不减1 // 找右边界, 这数在最左侧的索引 while (left < right) { 
         int mid = left + (right - left) / 2; if (nums[mid] > target) { 
         right = mid; } else if (nums[mid] < target) { 
         left = mid + 1; //  } else if (nums[mid] == target) { 
         left = mid + 1; // 相等时赋值不同，右边界给left赋值，继续往右找，所以left = mid + 1，左边界给right赋值，继续往左找，right = mid } } return right - 1; // 右侧值减1，原因是获取到mid后区间被划分成[mid + 1, right)，导致left的值加1，索引往后移动了1 } 

    vector<int> searchRange(vector<int>& nums, int target) { 
       
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);

        vector<int> res(2, 0);
        if (left <= right && nums[left] == target && nums[right] == target) { 
       
            res[0] = left;
            res[1] = right;
        } else { 
       
            res[0] = -1;
            res[1] = -1;
        }
        return res;
    }

电容的最小消耗速度（左边界）

class Solution { 
       
public:
    bool isFinsh(vector<int>& piles, int midSpeed, int H)
    { 
       
        int time = 0;
        for (auto pile : piles) { 
       
            int yu = pile % midSpeed > 0 ? 1 : 0;
            time += (pile / midSpeed + yu); // 涉及到小数一定要看余数(错写成 pile / midSpeed + 1)
        }
        return time <= H;
    }
    int minEatingSpeed(vector<int>& piles, int H) { 
       
        int sum = 0;
        for (auto pile : piles) { 
       
            sum += pile;
        }

        int left = 0;
        int right = sum;
        while (left < right) { 
       
            int midSpeed = left + (right - left) / 2; // 下一次的索引区间[left mid] [mid + 1 right]

            if (isFinsh(piles, midSpeed, H)) { 
       
                right = midSpeed; // 所以此处的right 没有 - 1
            } else { 
       
                left = midSpeed + 1;
            }
        }
        return left; // 返回最小的消耗速度
    }
};

负载均衡 题目见.cpp记录，思路和上述相同

class Solution { 
       
public:
    bool isSatisfy(int load, int serverNum, vector<int> task)
    { 
          
        int needServe = 0;
        for (auto t : task) { 
       
            int yu = t % load;
            needServe += (t / load + (yu > 0 ? 1 : 0)); // 余数单独写一行，+的优先级要高于 >
        }
        return needServe <= serverNum;
    }

    int minLoader(int serverNum, vector<int> tasks)
    { 
       
        int sumTask = 0;
        for (auto task : tasks) { 
       
            sumTask += task;
        }

        int left = 0;
        int right = sumTask; // []

        while (left < right) { 
       
            int load = left + (right - left) / 2;
            if (isSatisfy(load, serverNum, tasks)) { 
        // 满足，让值更小
                right = load; // 满足条件的边界没有加减操作
            } else { 
       
                left = load + 1; // 右侧的反方向对应左侧就 + 1;
            }
        }
        return left;
    }
};

展厅容纳最大人数总和小于cnt（右边界） N个展厅，每个展厅人数nums，所有展厅人数和上限cnt 计算单个展厅最大参展人数limit

思路 二分查找获取右边界

class Solution { 
       
public:
    int isFinsh(const vector<int> &nums, int midLimit, int cnt)
    { 
       
        int numSunm = 0;
        for (auto num : nums) { 
       
            if (num >= midLimit) { 
       
                numSunm += midLimit;
            } else { 
       
                numSunm += num;
            }
        }
        return numSunm <= cnt ? true : false;
    }

    int ManageTourists(const vector<int> &nums, int cnt)
    { 
       
        uint32_t numsSum = 0;
        for (auto num : nums) { 
       
            numsSum += num;
        }

        if (numsSum <= cnt) { 
       
            return -1;
        }
        
        uint32_t leftLimit = 0;
        uint32_t rightLimt = numsSum;

        while (leftLimit < rightLimt) { 
       
            uint32_t midLimit = leftLimit + (rightLimt - leftLimit) / 2;
            if (isFinsh(nums, midLimit, cnt)) { 
       
                leftLimit = midLimit; // 满足的情况，该值后续也需要计算，此处赋值不需要加1，else分支不满足，赋值需要减1
            } else { 
       
                rightLimt = midLimit - 1; // 人数过多，总和大于cnt
            }

        }
        return leftLimit;
    }
};

吃香蕉 N堆香蕉num[N]，第i 堆有香蕉num[i]个 需要在H小时吃完，每小时最多吃一堆香蕉，问每小时至少需要吃多少根 sort排序N堆香蕉 每小时吃最多num[N]肯定能吃完，但是不满足最少，所以很显然就需要用到二分来遍历速度 0 - num[N]根/h，找到左侧边界 先写左边界的模板 这里条件判断不再是简单的num[mid] 与 left/right比较，需要看当前的速度是否能吃完所有香蕉 完善isFinsh()接口，入参速度 H小时 数组，num[i]/speed整数部分累加，余数 > 0需要加1，否则加0

码头运送货物

差分/二分法

二分查找区间的考试题，部分用例通过

寻找一个数 入参num[] target

left right while(left <= right) 不等更新left/right，相等返回 mid

在指定数组中找目标元素 nums = [-1,0,3,5,9,12], target = 9 正常思路都是遍历nums，判断当前值是否与目标值相等。对于目标元素9，如果采用二分查找只需要查找 2次，遍历需要查找 5次

1. 下标二分后，获取对应下标元素与目标值比较。不是元素二分
2. 计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出
3. 二分查找的前提条件：集合有序
4. 搜索左右侧边界（左侧比target小的数的索引，右侧比target大的数的索引） 循环时找到中位数后不能直接返回 需要一直while循环，最终根据while(left <= right)条件判断