Given the ratings of the classes, answer each query with the smallest absolute difference between the query value and any class rating. Sort the ratings once in ascending order, then use binary search to find each query’s insertion point.
Only the ratings immediately before and after the insertion point can be nearest. Every rating farther to the left is no greater than the left neighbor, and every rating farther to the right is no smaller than the right neighbor. Therefore, neither side can contain a closer rating than its neighbor. At either end of the array, compare only the neighbor that exists. Duplicate ratings are handled naturally.
Compute each difference as a long so the subtraction and absolute value cannot overflow an int. Sorting takes O(N log N) time, and each of the Q queries takes O(log N), for O((N + Q) log N) total time. The ratings array uses O(N) space.
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return sign * value;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int n = input.nextInt();
int[] ratings = new int[n];
for (int i = 0; i < n; i++) {
ratings[i] = input.nextInt();
}
Arrays.sort(ratings);
int q = input.nextInt();
StringBuilder output = new StringBuilder();
for (int i = 0; i < q; i++) {
int target = input.nextInt();
int low = 0;
int high = n;
while (low < high) {
int middle = low + (high - low) / 2;
if (ratings[middle] < target) {
low = middle + 1;
} else {
high = middle;
}
}
long answer = Long.MAX_VALUE;
if (low < n) {
answer = Math.abs((long) ratings[low] - target);
}
if (low > 0) {
answer = Math.min(answer, Math.abs((long) ratings[low - 1] - target));
}
output.append(answer).append('\n');
}
System.out.print(output);
}
}