之前先学了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; }
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()选择区间的条件
得用两次二分，找到左右两个值
#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; }
