前言:
😁主页:战士小小白的博客
🍃年级:大二学生
🏆爱好:coding、足球(前青岛市足协运动员)
🍄主要内容:算法、计算机核心课程知识点、有趣黑科技等
🎻欢迎关注,欢迎留言讨论
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回
-1 -1
。
分析:先找最左边的x,check函数为要找的整数区间,在x的右边,所以是qmid >= x, x在mid的左边,所以x所在区间为l, mid。再找最右边的x,check函数为要找的整数区间,在x的左边,所以是qmid <= x, x在mid的右边,所以x所在区间为mid, r。
#include <bits/stdc++.h>
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;
else l = mid + 1;
}
if(q[l] != x) cout << "-1 -1" << endl;//q[l] 和 q[r] 是一样的
else
{
cout << l << " " ;
//二分最右边
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= x) l = mid;//l = mid 时候 上一行 改成 l + r + 1
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
给定一个浮点数 nn,求它的三次方根。
#include <bits/stdc++.h>
using namespace std;
int main()
{
double x;
//cin >> x;
scanf("%le", &x);
double l = -10000, r = 10000;
while(r - l > 1e-8)//大于这个精度表示没二分完全,执行代码
{
double mid = (l + r) / 2;
if(mid * mid * mid >= x) r = mid;
else l = mid;
}
printf("%lf\n", l);
return 0;
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。