二分搜索的不同情况

二分搜索可以用来查找满足条件的值，但是满足条件的值可能只有1个，也可能有多个。比如查找1的索引，对于【1，1，2，2】来说，就有2个。一般要求的就是：满足条件最大值/满足条件最小值。
二分搜索详细介绍可以参考：https://programmercarl.com/0704.二分查找.html#思路 这里不赘述了。

一般查找唯一满足条件的值

可以mid满足条件直接return

int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值，直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }

二分查找最大

获取值<=k的最大值，a[mid] = k也继续向右找

int uperK(int a[], int k){
        int l = 0;
        int r = a.length - 1;
        while(l < r){
            int mid = (l + r ) / 2;
            if(a[mid] <= k) { //a[mid] = k也继续向右找
                l = mid;
            }else{
                r= mid - 1;
            }
        }
        // 没有办法得到了
        if(a[l] > k) return -1;
        return a[l];
    }

二分查找最小

获取值<=k的最小值，a[mid] = k向左找

int uperK(int a[], int k){
        int l = 0;
        int r = a.length - 1;
        while(l < r){
            int mid = (l + r ) / 2;
            if(a[mid] < k) { //a[mid] = k向左找
                l = mid;
            }else{
                r= mid - 1;
            }
        }
        // 没有办法得到了
        if(a[l] > k) return -1;
        return a[l];
    }

错题笔记

https://www.lanqiao.cn/problems/99/learning/?page=1&first_category_id=1&tag_relation=union&tags=前缀和,二维前缀和,二分,差分

错误代码：mid就直接return，没考虑到不同边长切出来巧克力块数可能一样，比如5×5的，能切成1个5×5，或者1个4×4，或者1个3×3，都是1个。

n, k = map(int, input().split())
chocolate = [list(map(int, input().split())) for _ in range(n)]
left=1
right=100000
def count(mid):
    sum=0
    for a,b in chocolate:
        sum+=(a//mid)*(b//mid)
    return sum

def binsearch(l,r):
    while l<=r:
        mid=(l+r)//2
        sum=count(mid)
        if sum>k:l=mid+1
        elif sum<k:r=mid-1
        else:return mid   //错误
    return r

print(binsearch(left,right))

AC代码

n, k = map(int, input().split())
chocolate = [list(map(int, input().split())) for _ in range(n)]
left=1
right=100000
def count(mid):
    sum=0
    for a,b in chocolate:
        sum+=(a//mid)*(b//mid)
    return sum

def binsearch(l,r):
    while l<=r:
        mid=(l+r)//2
        sum=count(mid)
        if sum>=k:l=mid+1
        elif sum<k:r=mid-1
    return r

print(binsearch(left,right))

来源链接：https://www.cnblogs.com/dinosauria/p/18710287