题目描述
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。
第二行包含 n 个整数(均在 1∼10000 范围内),表示完整数组。
接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
样例
输入样例
6 3
1 2 2 3 3 4
3
4
5
输出样例
3 4
5 5
-1 -1
题目分析
对于一个升序排列的数组中,查找某一个指定元素x,如果找不到则返回-1;如果能找到则返回不小于此元素的最小位置和不大于此元素的最大位置。
因此需要两个二分代码,一个用于寻找>=x的第一个元素的位置,一个用于寻找<=x的最后一个元素的位置。
整数二分Java版代码模板
public static Integer bsearch_1(int q[], int l, int r, int x) {
while (l < r) {
int mid = l + r >> 1;
if (check1(q, mid, x)) r = mid;
else l = mid + 1;
}
return 1;
}
public static Integer bsearch_2(int q[], int l, int r, int x) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check2(q, mid, x)) l = mid;
else r = mid - 1;
}
return 1;
}
对于查找>=x的第一个元素位置的代码(包括check函数的判断和二分)
public static boolean check1(int q[], int mid, int x) {
if (q[mid] >= x) return true;
else return false;
}
public static Integer bsearch_1(int q[], int l, int r, int x) {
while (l < r) {
int mid = l + r >> 1;
if (check1(q, mid, x)) r = mid;
else l = mid + 1;
}
if (q[l] != x) return -1;
else return l;
}
对于查找<=x的第一个元素位置的代码(包括check函数的判断和二分)
public static boolean check2(int q[], int mid, int x) {
if (q[mid] <= x) return true;
else return false;
}
public static Integer bsearch_2(int q[], int l, int r, int x) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check2(q, mid, x)) l = mid;
else r = mid - 1;
}
//循环结束后,l == r
if (q[l] != x) return -1;
else return l;
}
完整代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
整数二分
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
//输入数组长度 n 和 查询个数 q
int n = Integer.parseInt(s1[0]);
int q = Integer.parseInt(s1[1]);
//输入完整数组并存储到一个整数数组中
String[] s2 = br.readLine().split(" ");
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(s2[i]);
}
//输入要询问的元素
int[] k = new int[q];
for (int i = 0; i < q; i++) {
k[i] = Integer.parseInt(br.readLine());
}
for (int i = 0; i < q; i++) {
System.out.println(bsearch_1(arr, 0, n - 1, k[i]) + " " + bsearch_2(arr, 0, n - 1, k[i]));
}
}
//整数二分模板
public static Integer bsearch_1(int q[], int l, int r, int x) {
while (l < r) {
int mid = l + r >> 1;
if (check1(q, mid, x)) r = mid;
else l = mid + 1;
}
if (q[l] != x) return -1;
else return l;
}
public static Integer bsearch_2(int q[], int l, int r, int x) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check2(q, mid, x)) l = mid;
else r = mid - 1;
}
//循环结束后,l == r
if (q[l] != x) return -1;
else return l;
}
//check函数
public static boolean check1(int q[], int mid, int x) {
if (q[mid] >= x) return true;
else return false;
}
public static boolean check2(int q[], int mid, int x) {
if (q[mid] <= x) return true;
else return false;
}
}
注意
一个题目,如果一个区间具有单调性质,那么一定可以二分,但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分. ——y总 https://www.acwing.com/solution/content/2104/