Median

来源POJ第3579题Median

Description

Given N numbers, X1, X2, … , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

Input

The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, … , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

Output

For each test case, output the median in a separate line.

Sample Input

4
1 3 2 4
3
1 10 2

Sample Output

1
8

一共有n*(n-1)/2种不同的配对，一一枚举的时间复杂度为O(n^2)，显然无法在1s内给出答案。在此使用二分法，先将数组排序，然后我们可以确定最大的距离为Xn-X1，那么我们只需要在0~|Xn-X1|，这些数之间寻找中位数即可。

一共需要两次二分。第一次二分，是用来寻找（猜测）可能的中位数的大小，当我们选择了一个mid值，我们需要计算有多少组配对的距离是小于这个mid值，如果不到k/2，则需要增加mid值，反之亦然；第二次二分用于对特定的元素计算小于mid的距离点对有多少个。

需要注意的是，在发现小于mid的点对刚好是一半的时候，并不能说明mid就是中位数，我们一定要找到满足这一性质最小的mid，才是最终的答案。

import java.util.*;

public class Main {

	public static int[] nums;
	public static long Mid;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n;
		while (in.hasNext()) {
			n = in.nextInt();
			Mid = ((long) n * (n - 1)) >> 1;
			Mid = (Mid + 1) >> 1; //中位数的位置
			nums = new int[n];
			for (int i = 0; i < n; ++i) {
				nums[i] = in.nextInt();
			}
			Arrays.sort(nums);
			int left = -1;
			int right = nums[n - 1] - nums[0] + 1;
			while (right - left > 1) {//二分搜索
				int mid = (left + right) >> 1;
				if (test(mid,n)) {
					right = mid;
				} else
					left = mid;
			}
			System.out.println(right);
		}
	}

	public static boolean test(int mid, int n) {
		int j = 0;
		int count = 0;
		for (int i = 1; i < n; i++) {
			while (nums[i] - nums[j] > mid)
				j++;
			count += (i - j);
		}
		return count >= Mid;
	}
}