问题：
这是来自 LeetCode 的一个问题：
给定一个整数数组，返回其中所有元素中第 k 小的差值。一对数字 (A, B) 的差值定义为 A 和 B 之间的绝对差。
示例：
Input:
nums = [1,3,1]
k = 1
Output: 0
Explanation:
Here are all the pairs:
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
Then the 1st smallest distance pair is (1,1), and its distance is 0.
我的问题
我用一个朴素的方法O(n^2)解决了它，基本上我找到了所有的距离并对其进行排序，然后找到第k小的距离。现在有一个更好的解决方案。这不是我的代码，我在leetcode的讨论论坛上发现的。但我在理解代码的一个关键部分时遇到了麻烦。
下面的代码基本上执行二分搜索。 low 是最小距离，high 是最大距离。像通常的二分搜索一样计算 mid。然后执行 countPairs(a, mid) 来查找绝对差小于或等于 mid 的配对数。然后相应地调整 low 和 high。
但为什么二分搜索的结果必须是其中一个距离？起初，low 和 high 是从数组中获取的，但是 mid 是由它们计算的，它可能不是距离。最后，我们返回了 low，而随着 mid + 1 的变化，它的值在二分搜索中发生了变化。为什么 mid + 1 保证是其中一个距离？
class Solution {
// Returns index of first index of element which is greater than key
private int upperBound(int[] a, int low, int high, int key) {
if (a[high] <= key) return high + 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (key >= a[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Returns number of pairs with absolute difference less than or equal to mid.
private int countPairs(int[] a, int mid) {
int n = a.length, res = 0;
for (int i = 0; i < n; i++) {
res += upperBound(a, i, n - 1, a[i] + mid) - i - 1;
}
return res;
}
public int smallestDistancePair(int a[], int k) {
int n = a.length;
Arrays.sort(a);
// Minimum absolute difference
int low = a[1] - a[0];
for (int i = 1; i < n - 1; i++)
low = Math.min(low, a[i + 1] - a[i]);
// Maximum absolute difference
int high = a[n - 1] - a[0];
// Do binary search for k-th absolute difference
while (low < high) {
countPairs(a, mid)
if (countPairs(a, mid) < k)
low = mid + 1;
else
high = mid;
}
return low;
}
}
k=100，lo=0，hi=18，并且我们有mid=9。由于countPairs(a,9)=99<100，我们将更新lo=mid+1。现在我们有k=100，lo=10，hi=18。下一次搜索时，我们将查看的是countPairs(a,14)而不是countPairs(a,10)。 - OLIVER.KOO