Algorithm10 二分
[TOC]
二分
查找的几种：
- 暴力遍历：
O(n)- 折半查找/二分查找：
O(log2n)- 哈希：
O(1)其中，二分就是折半查找。
关键点：等于号的选取、l/r的区间范围的更改、check函数
整数二分
1 => l <= r
while (l <= r) {
mid = (l+r)>>1;
if (mid == 0) {ans = mid;break;}
if (check(mid)) l = (ans=mid)+1;
else r = mid-1;
}
2 => l+1 < r
while (l + 1 < r) {
mid = (l + r) / 2;
if (f(mid)) l = mid;
else r = mid;
}
cout << l << endl;
https://www.luogu.com.cn/problem/P1024
题目大意：
#include <iostream>
using namespace std;
double a, b, c, d, l, r, tl, tr, mid;
double compute(double x) {return a*x*x*x+b*x*x+c*x+d;}
int main() {
scanf("%lf%lf%lf%lf", &a, &b, &c, &d);
for (int i = -100; i < 100 ; ++i) {
l = i,r = i+1;
tl = compute(l), tr = compute(r);
// printf("%d == %.2lf == %.2lf\n", i, tl, tr);
if (tl == 0) printf("%.2lf ", l);
// 限定了单个解的区间之后，进行二分
if (tl*tr < 0){
// printf(" -------- %d -- %d\n", l, r);
while (r-l >= 0.001) {
mid = (r+l)/2;
if (compute(mid) * compute(r) <= 0) l = mid;
else r = mid;
}
printf("%.2lf ", r);
}
}
return 0;
}
整数二分
https://www.luogu.com.cn/problem/P1873
题目大意：求最高的切割高度，满足切下来的总长度大于要求的
整数二分+特殊情况特判 （=>也就是二分不出结果的情况）
https://www.luogu.com.cn/problem/P2440
#include <iostream>
using namespace std;
#define maxn 1000100
typedef long long LL;
LL k;
int n, a[maxn], l, r, mid, ans;
bool check(int mid) {
LL cnt = 0;
for (int i = 1; i <= n; ++i) cnt += (a[i]/mid);
return cnt >= k;
}
int main() {
scanf("%d%lld", &n, &k);
for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]);r = max(r, a[i]);}
while (l <= r) {
mid = (l+r)>>1;
if (mid == 0) {ans = mid;break;}
if (check(mid)) l = (ans=mid)+1;
else r = mid-1;
}
printf("%d\n", ans);
return 0;
}
整数二分
https://www.luogu.com.cn/problem/P2678
1、check函数的写法 => 通过二分最小的跳跃距离。
#include <iostream>
using namespace std;
#define maxn 50010
typedef long long LL;
#define INF (1<<31)-1
int n, m, a[maxn], l=INF, r, mid, ans;
LL len;
#include <algorithm>
bool check(int mid) {
int last=0, cnt=0;
for(int i = 1; i <= n; ++i){
if (a[i]-last<mid) cnt++;
else last = a[i];
}
if (len-last<mid) cnt++;
// printf("----- %d %d\n", mid, cnt);
return cnt<=m;
}
int main() {
scanf("%lld%d%d", &len, &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
sort(a+1, a+1+n);
l = 1,r = len+1;
while (l+1 < r) {
mid = (l+r)>>1;
if (check(mid)) l = (ans=mid);
else r = mid;
}
printf("%d\n", ans);
return 0;
}
小数二分
https://www.luogu.com.cn/problem/P1163
特殊二分
https://www.luogu.com.cn/problem/P1678
在二分的过程中找最小的遍历到的最小，二分搜索到的那个并不一定是最佳的，所以在遍历的过程中进行判断
题目大意：m个学校，n个学生，给每个学生找到绝对值的差值最小的分数的学习（低了高了都行）
1、每个学生都进行一遍二分，然后最后在二分的遍历过程中获取最小的和
#include <iostream>
using namespace std;
#define maxn 100010
int m, n, a[maxn], b[maxn], total;
#define INF (1<<31)-1
#include <algorithm>
int main() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
sort(a+1, a+1+m);
for (int i = 1; i <= n; ++i) {
int l = 1, r = m, mid, ans=INF;
while (l <= r) {
mid = (l+r)>>1;
if (b[i] > a[mid]) {l = mid+1;ans = min(ans, abs(a[mid]-b[i]));}
else {r = mid-1;ans = min(ans, abs(a[mid]-b[i]));}
}
total += ans;
}
printf("%d\n", total);
return 0;
}
STL 二分 - lowerbound & upperbound
0、理解：lower upper不理解为大小，而理解为边界，因为在单增和单减的情况下，所确定的大小关系是灵活的，但是边界选取的情况都是一致的，lower是上边界闭区间，upper是上边界开区间
1、【大前提：必须是在已经排好序的情况下】在递增和递减的序列中的有不同的作用。
2、指针类型的使用方法，类似于排序的参数传入(a, a+n)-n，想返回索引就要把首地址给减了走
int a = {1, 2, 6, 7, 14, 35}, targetnum = 7;
int pos1 = lowerbound(a, a+6, targetnum)-a; // 输出 大于等于 targetnum(7) 的数的索引位置 => 3，也就是第4个数
int pos2 = upperbound(a, a+6, targetnum)-a; // 输出 大于 targetnum(7) 的数的索引位置 => 4，也就是第5个数
int b = {35, 14, 7, 6, 2, 1};
int pos3 = lowerbound(b, b+6, targetnum)-b; // 输出 小于等于 targetnum(7) 的数的索引位置 => 2，也就是第3个数
int pos4 = upperbound(b, b+6, targetnum)-b; // 输出 小于 targetnum(7) 的数的索引位置 => 3，也就是第4个数