Java 二分法
程序员文章站
2024-03-16 08:52:58
...
整数二分法
首先二分法属于分治算法,通过不断二分数组来寻找某一个数,这里牵扯到一个分界点问题
寻找左分界点
private static int f(int l, int r) {
while(l < r) {
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
寻找右分界点
private static int f(int l, int r) {
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
这两套模板需要选择什么时候用哪个
【例题】
给定一个按照升序排列的长度为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
样例
输入:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
【题解】
import java.util.Scanner;
public class Main {
static int N = 100010;
static int[] f = new int[N];
static int n, q;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
q = sc.nextInt();
for (int i = 0; i < n; i++) f[i] = sc.nextInt();
while (q -- > 0) {
int k = sc.nextInt();
int l = 0, r = n - 1;
while (l < r) {
int mid = r + l >> 1;
if(f[mid] >= k) r = mid;
else l = mid + 1;
}
if(f[l] != k) System.out.println("-1 -1");
else {
System.out.print(r + " ");
l = 0; r = n - 1;
while(l < r) {
int mid = r + l + 1 >> 1;
if(f[mid] <= k) l = mid;
else r = mid - 1;
}
System.out.print(r + "\n");
}
}
}
}
浮点数二分法
浮点数二分法需要注意精度问题,计算的时候比题目中保留小数位多两位就行了,不需要想边界问题。
模板
private static double f(double l, double r) {
while(r - l > 1e-8) {
double mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
return l;
}
【例题】
给定一个浮点数n,求它的三次方根。
输入格式
共一行,包含一个浮点数n。
输出格式
共一行,包含一个浮点数,表示问题的解。
注意,结果保留6位小数。
数据范围
−10000≤n≤10000
输入样例:
1000.00
输出样例:
10.000000
【题解】
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
double n = Double.parseDouble(reader.readLine());
double l = -10000, r = 10000;
while(r - l > 1e-8) {
double mid = ( l + r ) / 2;
if(mid * mid * mid >= Math.abs(n)) r = mid;
else l = mid;
}
if(n < 0) System.out.print("-");
System.out.printf("%.6f",r);
//writer.flush();
//writer.close();
reader.close();
}
}