从给定范围中找到数字的最高最小差

Question

假设我有一个数组，其中包含 N 个数字 {A1, A2, ... , An} 和 2 个数字 P, Q

我必须在 P 和 Q 之间找到一个整数 M，使得 min {|Ai-M|, 1 ≤ i ≤ N} 最大化。

1 < N < P ≤ Q ≤ 10^6

简单来说：

对于每个数字，找出该数字与数组之间的最小绝对差值。然后在所有这些最小差异中，找到最小差异最大的数字。

我必须在 O(NlogN) 或更短时间内完成此操作。

我试过以下方法：

我猜有某种数学运算 "trick" 比如使用平均数我想念..

编辑（添加示例）：

例如，如果你有数组 {5 8 14} P=4 Q=9

答案是 4、6、7 或 9。

让我们看看数字 4-9

|4-5| = 1
|4-8| = 4
|4-14| = 10

所以 4 的最小差异是 1

|5-5| = 0
|5-8| = 3
|5-14| = 9

所以 4 的最小差异是 0

我们继续寻找所有数字的最小差异，然后我们需要说出哪个数字 (4/5/6/7/8/9) 具有最高的最小差异（在本例中为 4,6， 7 和 9 有 1 个最小差，这是所有最小差中最大的）

Answer 1

首先你必须对数组进行排序。然后你必须注意到你的解决方案是 P 或 Q 或某个点 x[i] = (A[i] + A[i+1]) // 2。基本上x[i]在数组中连续元素之间（如果这个x[i]在P，Q之间）。

因为N真的很小，所以运行基本上O(1)。

Find the highest minimum difference of a number from a given range