二分法
二分模板:查找
给定n个数,然后询问m次,找个数在不在这个递增数列里,在就返回这个值,不在就返回-1.
测试样例:
5
2 5 6 9 10
4
9 6 4 10
#include <iostream>
using namespace std;
const int N = 1e4 + 9;
int a[N], n, m;
int binary_search(int x){
int l = 0, r = n-1;
while(l<=r){
int mid = (l+r)>>1;
if(a[mid] == x){
return mid;
}
if(a[mid]<x){
l = mid + 1;
}else {
r = mid - 1;
}
}
return -1;
}
int main() {
cin>>n;
for(int i = 0;i < n;++i){
cin>>a[i];
}
cin>>m;
while(m--){
int x;
cin>>x;
cout<< binary_search(x)<<endl;
}
return 0;
}
二分法在计算机中的应用
求根号下K的值
get_sqrt(k)
l = 0, r = k
while r - l > eps
mid = (l + r) / 2
if mid * mid <= k
l = mid
else
r = mid
return l
求方程的近似解
对于方程 x4 + 5 x 3 + 6 x 2 + 7 * x + 4 = y 接受一个参数y ,求[0,100]范围之内的解,并返回,要求精确三位小数,如果没有解,返回-1。
关键点,很明显是单调递增函数,可以用二分法。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-3;
double f(double x) {
return pow(x, 4) + 5 * pow(x, 3) + 6 * pow(x, 2) + 7 * x + 4;
}
double cal(double y){
if(f(0)>y || f(100)<y)
{
return -1;
}
double l = 0,r = 100;
while(r - l > eps){
double mid = ( l + r ) / 2;
if(f(mid) > y){
r = mid;
} else {
l = mid;
}
}
return l;
}
int main () {
double y;
cin>>y;
printf("%.3lf\n",cal(y));
return 0;
}
二分快速幂
每次要写二分快速幂模板的时候,想原理,关键点是二进制,和a2x = a2x-1 * a2x-1
int Pow_mod(int a, int b, int mod){
int res = 1, temp = a;
for (; b; b /= 2) {
if (b & 1) {
res = res * temp % mod; // 2 进制上这一位为 1,乘上这一位权值
}
temp = temp * temp % mod; // 位数加 1,权值平方
}
return res;
}
#include <iostream>
using namespace std;
int pw1 (int x, int y, int p){ //递归快速幂
if(!y){
return 1;
}
int res = pw1(x,y/2,p);
res = res*res%p;
if(y&1){
res = res*x%p;
}
return res;
}
int pw2 (int x, int y, int p){ //循环快速幂
int res = 1;
while(y){
if(y&1){
res = res*x%p;
}
y>>=1;
x = x*x%p;
}
return res;
}
int main() {
int x, y, p;
cin >> x >> y >> p;
cout << pw1(x,y,p) << endl;
cout << pw2(x,y,p) << endl;
return 0;
}
二分答案
8 4
1 3 4 7 1 4 3 8
一共有m个数,最多分为k组,其和为gi,对于每组数的总和的最大值最小可以是多少?
二分需要注意一点的是在于考虑边界
#include <iostream>
using namespace std;
const int N = 1e3 + 9;
const int inf = 0x3f3f3f3f;
int n, k, a[N];
bool check(int x){
int now = 0 ,cnt = 0;
for(int i = 0; i < n; ++i){
if(now + a[i] > x){
++cnt ;
now = a[i];
} else {
now += a[i];
}
}
return cnt <= k;
}
int cal(int l, int r){
while(l < r){
int mid = (l + r) >> 1;
if(check(mid)){
r = mid ;
} else {
l = mid + 1;
}
}
return l;
}
int main() {
int ma = -inf , sum = 0;
cin >> n >> k;
for(int i = 0; i < n ; ++i){
cin >> a[i];
ma = max(ma,a[i]);
sum += a[i];
}
cout << cal(ma, sum) << endl;
return 0;
}