题目大意
给定N个数，这些数字两两求差构成C(N,2)（即N*(N-1)/2）个数值，求这C(N,2)个数的中位数。N <= 100000.
题目分析
根据数据规模N最大为100000，可知不能直接求每两个数的查找（O(N*N)复杂度），然后排序，再求中位数。考虑使用二分法查找满足要求的中位数：
先将原数组排序，然后假设数k为中位数，那么如果这N个数字构成的C(N,2)个差值中小于k的小于C(N,2)/2个，则k需要增加；如果小于等于k的数字大于等于C(N,2)，那么k需要减少。最后求出的k是恰好满足C(N,2)个差值中小于等于k的数大于等于C(N,2)个，且差值中存在k 的最小值。
实现(c++)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MAX_N 100005 int an[MAX_N];
int DiffKLessThanHalf(int n, int k){
int sum = 0;
int max_pair = n*(n-1) / 2;
max_pair = max_pair / 2 + max_pair % 2; //小于等于中位数的最少个数
bool flag = false;
for (int i = 0; i < n - 1; i++){
int beg = i + 1, end = n;
while (beg < end){
int mid = (beg + end) / 2;
if (an[mid] - an[i] == k){ //差值中存在k，说明k可以做为中位数
flag = true;
}
if (an[mid] - an[i] <= k)
beg = mid + 1;
else
end = mid;
}
sum += (beg - i - 1); //和 an[i] 的差值小于等于k的个数 为 beg - i - 1
if (sum >= max_pair && flag)//小于等于k的个数 至少为C(N,2) 且 存在差值等于k，说明k可以作为一个中位数，
//但后续需要继续求满足这种条件的最小的k。直接返回
return 2;
}
if (sum < max_pair) //小于等于k的个数 小于 C(N,2)，说明中位数 > k
return 0;
return 1;
} int main(){
int n; while (scanf("%d", &n) != EOF){
for (int i = 0; i < n; i++){
scanf("%d", &an[i]);
}
sort(an, an + n);
int beg = 0, end = an[n-1] - an[0] + 1;
int rr = 0;
while (beg < end){
int mid = (beg + end) / 2;
int result = DiffKLessThanHalf(n, mid);
if (result == 0)
beg = mid + 1;
else if (result == 1){
end = mid;
}
else{
end = mid;
rr = mid; //记录下一个可能的中位数值
}
}
printf("%d\n", rr);
}
return 0;
}