AcWing 789,790. 二分法
原题链接
简单
数的范围
输入样例
6 3 //输入数的数量 查询次数
1 2 2 3 3 4 //输入的数
3 //查询的数
4
5
输出样例
3 4
5 5
-1 -1
整数二分
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n, q, k;
int s[N];
int main()
{
cin >> n >> q;
for (int i = 0; i < n; i++)
scanf("%d", &s[i]);
while (q--)
{
cin >> k;
/*模板一*/
int l = 0,r = n - 1;
while (l < r)
{
int mid = l + r >> 1;//寻找左边界,即r=mid,mid不需要加一
if (s[mid] >= k)
r = mid;
else
l = mid + 1;
}
if (s[l] != k)//如果查询的数不存在
cout << "-1 -1" << endl;
else
{
cout << l << ' ';
/*模板二*/
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;//寻找右边界,即l=mid,mid需要加一(上取整)
if (s[mid] <= k)
l = mid;
else
r = mid -1;
}
cout << l << endl;
}
}
return 0;
}
数的三次方根
输入样例
1000.00
输出样例
10.000000
浮点数二分
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
double n;
cin >> n;
double l = -10000, r = 10000;
while (r - l > 1e-8)//保证精确度
{
double mid = (l + r) / 2;
if (mid * mid * mid >= n)
r = mid;
else
l = mid;
}
printf("%lf\n", l);
return 0;
}