根据视频整理, 结合视频看效果更佳
整数二分法模板
二分的本质不是单调性, 单调性的题目一定可以二分, 可以二分的题目不一定有单调性
二分的本质是边界
二分法用于查找, 每次都选择答案所在的区间再次进行查找, 当区间长度为 1时, 就是答案
模板一
// 区间[l, r]被划分成 [l, mid] 和 [mid+1, r]时使用
int bsearch_1(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check[mid) // check() 判断 mid是否满足性质
r = mid;
else
l = mid + 1;
}
return l;
}
模板二
// 区间[l, r]被划分成 [l, mid-1] 和 [mid, r]时使用
int bsearch_2(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 2; // 注意
if (check[mid) // check() 判断 mid是否满足性质
l = mid;
else
r = mid - 1;
}
return l;
}
如何选择模板
- 根据 check(mid)来判断 r和 l的取值范围
- 根据取值范围选择 mid是否有 + 1操作
- mid归于左边, r = mid, mid选择 不 +1
- mid归于右边, l = mid, mid选择 +1
解答本题
思路
分别找出左边界和右边界
二分算法一定可以查找到解, 但是题目可能没有解
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 获取输入值
int n = in.nextInt(); // 数组大小
int count = in.nextInt(); // 查询个数
// 获取完整数组
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = in.nextInt();
// 查询 count轮
while (count-- != 0) {
int target = in.nextInt(); // 本轮查询的目标值
// 初始化 l和 r, 查找左边界
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (arr[mid] >= target) // 如果 mid满足, 需要向左寻找
r = mid;
else
l = mid + 1;
}
// 跳出循环时, l == r, 如果数组中不存在 target
if (arr[l] != target) {
System.out.println("-1 -1");
} else {
System.out.print(l + " "); // 注意输出值为下标
// 初始化 l和 r, 查找右边界
l = 0;
r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1; // 使用第二个模板
if (arr[mid] <= target) // 如果 mid满足, 需要向右寻找
l = mid;
else
r = mid - 1;
}
System.out.println(l);
}
}
}
}
模板二:这里【int mid = l + r + 1 >> 2; // 注意】写错了吧,应该是【 >>1 】吧
确实是他写错了
为什么运行不出来-1 -1啊
山本
哎呀,找到个Java版的,针不错,感谢大佬1