【算法修炼】二分查找最接近元素（最接近下标）

之前学习的二分模板基本都是：查找相等元素的下标、第一个大于等于元素的下标和第一个大于元素的下标。但题目往往会考察：与当前元素差值最小的元素下标、最小的差值、最小差值的元素等，这就需要在二分的基础上加一些修改。

查找最接近的元素（简单）

只需要用到："第一个大于等于key元素"的二分模板

考虑使用该函数后的返回值：

• 返回等于key元素的元素下标，也就是说直接找到了key，此时答案就是key元素自身。
• 返回数组长度，也就是说没有找到大于等于key的元素(数组中所有元素小于key)，此时答案就是num[idx-1]。
• 排除情况一的情况下，返回下标=0，说明key元素的值小于所有数组中元素，此时答案就是num[0]。
• 排除情况一的情况下，返回下标，此时说明找到了第一个大于key元素的值的下标，此时答案需要比较位于key元素左右两边的元素值，看哪边的差值更小，也就是：Math.min(num[idx] - key, key - num[idx])。

import java.util.*;
import java.io.*;

public class Main {
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static List<Integer> idx;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine().trim());
        String[] input = reader.readLine().trim().split(" ");
        int[] num = new int[n];
        for (int i = 0; i < n; i++) num[i] = Integer.parseInt(input[i]);
        int m = Integer.parseInt(reader.readLine().trim());
        while (m-- > 0) {
            // 查询最接近元素的给定值
            int k = Integer.parseInt(reader.readLine().trim());
            int idx = search(num, k);
            if (idx == 0) System.out.println(num[0]);
            else {
                if (idx == n) idx--;
                else if (Math.abs(num[idx - 1] - k) <= Math.abs(num[idx] - k)) {
                	// 当有多个元素差值相同时，输出最小的元素
                    idx--;
                }
                System.out.println(num[idx]);
            }
        }
    }
    // 找第一个大于等于key值的下标
    static int search(int[] num, int key) {
        int left = 0;
        int right = num.length;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (num[mid] >= key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
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

最近距离（中等）

上一题在找最接近的元素，本题在找最接近0的下标，本质还是一样的，因为要 |i - j|尽可能小，i是a数组中各元素的下标，j是0值元素的下标，那就是找最接近的0值元素下标，那么就可以单独存储0值元素的下标。

import java.util.*;
import java.io.*;

public class Main {
    static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static List<Integer> idx;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine().trim());
        String[] input = reader.readLine().trim().split(" ");
        idx = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (input[i].equals("0")) {
                // 记录0值的下标
                idx.add(i);
            }
        }
        // 二分先排序
        Collections.sort(idx);
        for (int i = 0; i < n; i++) {
            if (input[i].equals("0")) {
                writer.write(input[i] + " ");
            } else {
                // 返回结果是下标的下标
                int ans = search(i);
                if (ans == 0) {
                    writer.write(Math.abs(idx.get(ans) - i) + " ");
                } else {
                    if (ans == idx.size()) {
                        ans--;
                    } else if (Math.abs(idx.get(ans - 1) - i) < Math.abs(idx.get(ans) - i)) {
                        ans--;
                    }
                    writer.write(Math.abs(idx.get(ans) - i) + " ");
                }
            }
        }
        writer.flush();
    }
    // 找第一个大于key的下标位置
    static int search(int key) {
        int left = 0;
        int right = idx.size();
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (idx.get(mid) > key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
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
55