二分查找（my理解和模板）

 之前先学了y总的二分，后来又看了代码随想录的，感觉代码随想录的更好记忆

• 二分查找需要的数据必须是有序的。如果数据没有序，我们需要先排序，排序的时间复杂度最低是 O(nlogn)。
• 二分查找底层依赖的是数组，数组需要的是一段连续的存储空间，所以数据量太大不适合二分查找
• 查找的方法，顾名思义，就是若 target = arr[mid]，则查找成功（找到了目标值）返回 mid 值

🚥🚥🚥

根据check()来划分区间 

🚥🚥🚥

⭐整数二分 

划分为[l,mid]和[mid+1,r] 

int binary(int l,int r){
	while(l<r){
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	return l;
}

划分为[l.mid-1]和[mid,r]

int binary(int l,int r){
	while(l<r){
		int mid=(l+r+1)/2;
		if(check(mid)) l=mid;//如果先是l=mid,那么为(l+r+1).要+1
		else r=mid+1;
	}
	return l;
}

⭐ 浮点数二分

int binary(int l,int r){
	while(l-r>0.001){ //0.001可以又其他浮点数代替，但是都必须尽可能小
		int mid=(l+r)/2;
		if(check(mid)) r=mid;//l=mid
		else l=mid;          //r=mid
	}                        //根据check()决定
	return l;
}

35. 搜索插入位置 – 力扣（LeetCode）

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
       int l=0,r=nums.size();
       while(l<r)
       {
           int mid=(l+r)/2;
           if(nums[mid]>target) r=mid;
           else if(nums[mid]<target) l=mid+1;
           else
           return mid;
       }
       return l;
    }
};

P1024 [NOIP2001 提高组] 一元三次方程求解 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<cstdio>
double a,b,c,d;
double fc(double x)
{
    return a*x*x*x+b*x*x+c*x+d;
}
int main()
{
    double l,r,mid,x1,x2;
    int s=0,i;
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);  
    for (i=-100;i<100;i++)
    {
        l=i; 
        r=i+1;
        x1=fc(l); 
        x2=fc(r);
        if(!x1) 
        {
            printf("%.2lf ",l); 
            s++;
        }      //判断左端点，是零点直接输出。
                        
                        //不能判断右端点，会重复。
        if(x1*x2<0)  //区间内有根。
        {
            while(r-l>=0.001)  //二分控制精度。
            {
                mid=(l+r)/2;  
                if(fc(mid)*fc(r)<=0) 
                   l=mid; 
                else 
                   r=mid;   //计算中点处函数值缩小区间。
            }
            printf("%.2lf ",r);  
            //输出右端点。
            s++;
        }
        if (s==3) //每找到一个，s++，当s=3时，就找到了3个
            break;             
            
    }
    return 0;
}

🚥🚥🚥 

下面这个题可以体会到check()选择区间的条件

789. 数的范围 – AcWing题库

得用两次二分，找到左右两个值

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;//>=x
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';

            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;//<=x
                else r = mid - 1;
            }

            cout << l << endl;
        }
    }

    return 0;
}

P8647 [蓝桥杯 2017 省 AB] 分巧克力 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 建议听听这个视频讲解http://【P8647 [蓝桥杯 2017 省 AB] 分巧克力】https://www.bilibili.com/video/BV1sx4y1L7Xq?vd_source=21581d752de8daca00ef38561a7264f6

或者

AcWing 1227. 分巧克力（寒假每日一题） – AcWing 

注意是长和宽，得开二维数组 

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, k;
int h[N], w[N];

bool check(int mid)
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += (h[i] / mid) * (w[i] / mid);
        if (res >= k) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);

    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);

    return 0;
}