二分·ACWING 789 790
整数二分
题目描述:
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1
。
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。
第二行包含 n 个整数(均在 1∼10000 范围内),表示完整数组。
接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1
。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
思路整理:
先找上半部分的下确界,再找下半部分的上确界,注意条件的不同以及边界的判定。
代码:
import java.util.Scanner;
public class Main {
static int mid = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int q = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
while (q-- > 0) {
int k = scanner.nextInt();
find(0, n - 1, k, arr);
}
scanner.close();
}
public static void find(int l, int r, int tar, int[] m) {
int a = 0;
int b = 0;
while (l < r) {
mid = l + r + 1 >> 1;//向下取整,以[0,1]为例
if (m[mid] <= tar)//等号,因为要找的是下确界
l = mid;
else {
r = mid - 1;//不满足条件,右边界必然在左边
}
}
if (m[(l + r + 1) >> 1] == tar) {
a = (l + r + 1) >> 1;
} else {//不存在,可直接排除
a = -1;
b = -1;
System.out.println(a + " " + b);
return;
}
l = 0;
r = m.length - 1;
while (l < r) {
mid = l + r >> 1;//向下取整,所以是不能加一的
if (m[mid] >= tar)
r = mid;
else {
l = mid + 1;
}
}
if (m[(l + r) >> 1] == tar) {
b = (l + r) >> 1;
System.out.println(b + " " + a);
} else {
b = -1;
}
}
}
小数二分
题目:
给定一个浮点数 n,求它的三次方根。
输入格式
共一行,包含一个浮点数 n。
输出格式
共一行,包含一个浮点数,表示问题的解。
注意,结果保留 6 位小数。
数据范围
−10000≤n≤10000
输入样例:
1000.00
输出样例:
10.000000
思路整理:
经典二分。
代码:
import java.util.Scanner;
public class Main{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
double k = sc.nextDouble();
double p = -10000;
double q = 10000;//无脑上下界选取
double mid = 0;
while(Math.abs(mid*mid*mid-k)>1e-10)//选取恰当精度,一般比要求保留的小数大两位
{ mid=(q+p)/2;
if(mid*mid*mid>k)//绝对值也可先加在k上
{q=mid;}
else
{p=mid;}
}
System.out.println(String.format("%.6f", mid));
}
}