二分模板

https://www.acwing.com/problem/content/791/

二分的本质不是单调性, 单调性的题目一定可以二分, 可以二分的题目不一定有单调性

二分的本质是边界
二分法用于查找, 每次都选择答案所在的区间再次进行查找, 当区间长度为 1时, 就是答案

  1. 根据 check(mid)来判断 r和 l的取值范围
  2. 根据取值范围选择 mid是否有 + 1操作
    • mid归于左边, r = mid, mid选择 不 +1
    • mid归于右边, l = mid, mid选择 +1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 模板_二分 {

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int[] line1 = Arrays.asList(input.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
        int n = line1[0];
        int q = line1[1];
        int[] line2 = Arrays.asList(input.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();

        while (q-- != 0) {
            int target = Integer.parseInt(input.readLine());
            // 查找左边界 用第一个模板
            int index_l = bsearch_1(line2, 0, n - 1, target);
            if (line2[index_l] != target) {
                System.out.println("-1 -1");
            } else {
                System.out.print(index_l + " ");
                // 查找右边界 用第二个模板
                int index_r = bsearch_2(line2, 0, n - 1, target);
                System.out.print(index_r + "\n");
            }
        }
    }

    public static int bsearch_1(int[] arr, int l, int r, int target) {
        while (l < r) {
            int mid = l + r >> 1;
            if (arr[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public static int bsearch_2(int[] arr, int l, int r, int target) {
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

}