目录
找和目标值相关
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)); // 输出 7
System.out.println("大于等于 " + x + " 的最小值: " + lowerBound(arr, x)); // 输出 7
System.out.println("小于 " + x + " 的最大值: " + floor(arr, x)); // 输出 5
System.out.println("小于等于 " + x + " 的最大值: " + ceiling(arr, x)); // 输出 5
}
}方法 Arrays.binarySearch();
题解
// @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 {
// todo
int 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);