二分查找
博客地址:https://blog.csdn.net/WJPnb1/article/details/126360962?spm=1001.2014.3001.5502
通用模版
int L=-1,R=n;
while(L+1!=R)
{
int mid=L+R>>1;
if(check()) L=mid;
else R=mid;
//最后根据你所分左右两边区间的结果
//选取L或者R作为结果
}
下面这个题的两种情况:
1 2 2 3 3 4
L R
L R
code 数的范围
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, q;
int a[N];
int main()
{
cin >> n >> q;
for(int i = 0; i < n; ++i) cin >> a[i];
while(q --){
int k;
cin >> k;
int l = -1, r = n;
while(l + 1 != r){
int mid = l + r >> 1;
if(a[mid] < k) l = mid;
else r = mid;
}
int res1 = r;
l = -1, r = n;
while(l + 1 != r){
int mid = l + r >> 1;
if(a[mid] <= k) l = mid;
else r = mid;
}
int res2 = l;
if(res1 > res2) cout << "-1 -1" << endl;
else cout << res1 << " " << res2 << endl;
}
}
code2: 数的三次方根
#include<iostream>
#include<math.h>
using namespace std;
const int N = 1e4 + 1;
double n;
int main()
{
double l = -N, r = N;
scanf("%lf", &n);
//这里不需要严格遵循模版来
while(r - l >= 1e-8){
double mid = (l + r) / 2.0;
if(mid * mid * mid < n) l = mid;
else r = mid;
}
printf("%.6lf", l);
}