欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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();
    }
}