算法竞赛相关 Java 二分模版
目录
找和目标值相关
方法 Arrays.binarySearch();
二分答案模版
找和目标值相关
public class BinarySearchTemplate {// 查找大于 x 的最小值（即严格上界）public static int upperBound(int[] arr, int x) {int left = 0, right = arr.length;while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] > x) {right = mid;} else {left = mid + 1;}}if(left<0||left>arr.length-1) {return -1; // -1 表示没有找到符合条件的元素}else {return arr[left]; }}// 查找大于等于 x 的最小值（即第一个不小于 x 的元素）public static int lowerBound(int[] arr, int x) {int left = 0, right = arr.length;while (left < right) {int mid = left + (right - left) / 2;if (arr[mid] >= x) {right = mid;} else {left = mid + 1;}}if(left < 0||left > arr.length-1) {return -1; // -1 表示没有找到符合条件的元素}else {return arr[left]; }}// 查找小于 x 的最大值（即严格下界）public static int floor(int[] arr, int x) {int left = -1, right = arr.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (arr[mid] < x) {left = mid;} else {right = mid - 1;}}if(left < 0||left > arr.length-1) {return -1; // -1 表示没有找到符合条件的元素}else {return arr[left]; }}// 查找小于等于 x 的最大值（即最后一个不大于 x 的元素）public static int ceiling(int[] arr, int x) {int left = -1, right = arr.length - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (arr[mid] <= x) {left = mid;} else {right = mid - 1;}}if(left < 0||left > arr.length-1) {return -1; // -1 表示没有找到符合条件的元素}else {return arr[left]; }}// 测试示例public static void main(String[] args) {int[] arr = {1, 3, 5, 7, 9, 11};int x = 6;System.out.println("大于 " + x + " 的最小值: " + upperBound(arr, x)); // 输出 7System.out.println("大于等于 " + x + " 的最小值: " + lowerBound(arr, x)); // 输出 7System.out.println("小于 " + x + " 的最大值: " + floor(arr, x)); // 输出 5System.out.println("小于等于 " + x + " 的最大值: " + ceiling(arr, x)); // 输出 5}
}方法 Arrays.binarySearch();
例题 P2249 【深基13.例1】查找 - 洛谷
题解
// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;/*** 题目地址**/// xixi♡西
public class Main {static IoScanner sc = new IoScanner();static final int mod = (int) (1e9 + 7);
// static final int mod = (int) (1e9 + 7);// static int n;
// static int arr[];
// static boolean visited[];
// static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();/*** @throws IOException*/private static void solve() throws IOException {// todoint n=sc.nextInt();int m=sc.nextInt();long arr[]=new long[n];for(int i=0;i<n;i++) {arr[i]=sc.nextLong();}StringBuilder sb=new StringBuilder("");for(int i=0;i<m;i++) {long target=sc.nextLong();int index = Arrays.binarySearch(arr, target);if (index >= 0) {while (index > 0 && arr[index - 1]==target) {index--;}} index+=1;if(index<1||index>n) {sb.append("-1 ");}else {sb.append(index+" ");}}dduoln(sb);}public static void main(String[] args) throws Exception {int t = 1;
// t = sc.nextInt();while (t-- > 0) {solve();}}static <T> void dduo(T t) {System.out.print(t);}static <T> void dduoln() {System.out.println("");}static <T> void dduoln(T t) {System.out.println(t);}
}/*** IoScanner类** @author Dduo* @version 1.0* @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。*/
class IoScanner {BufferedReader bf;StringTokenizer st;BufferedWriter bw;public IoScanner() {bf = new BufferedReader(new InputStreamReader(System.in));st = new StringTokenizer("");bw = new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException {return bf.readLine();}public String next() throws IOException {while (!st.hasMoreTokens()) {st = new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException {return next().charAt(0);}public int nextInt() throws IOException {return Integer.parseInt(next());}public long nextLong() throws IOException {return Long.parseLong(next());}public double nextDouble() throws IOException {return Double.parseDouble(next());}public float nextFloat() throws IOException {return Float.parseFloat(next());}public BigInteger nextBigInteger() throws IOException {return new BigInteger(next());}public BigDecimal nextDecimal() throws IOException {return new BigDecimal(next());}
}二分答案模版
long left=0;long right=(long) 1e9;long mid=0;while(left<right) {mid =left+(right-left)/2;if(judge(mid)==true) {right = mid;}else {left = mid+1;}}dduoln(left);