题意：
给定N（3 ≤N ≤ 1,00,000）个数，两两的差值，形成一个新序列，求这个新序列的中位数。
题解：
直接的是算出来两两的差值，然后再排序。这样以来时间复杂度来到了O（N2）,肯定会超时。
二分思想：每次判断Mid是否符合中位数：扫描一遍所有的数，计算每个数能与多少数构成差值小于Mid，将所有的小于Mid的数量加起来为cnt，判断cnt是否>=M（说明Mid选的太大了，同时也表明Mid这时候不为最优解）。
当然，如果前面找的是小于等于Mid的数量加起来，这时候就要判断cnt是否<M了。
这里给出两种AC代码！这种抽象的二分边界问题一定要搞清楚！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>using namespace std;int a[100000+5];
int n,M;
bool C(int x)
{ int cnt=0;for(int i=0;i<n;i++)cnt+=lower_bound(a+i,a+n,a[i]+x)-(a+i)-1;//与a[i]差值小于x的个数return cnt>=M;//满足此条件时，一定是x选的太了。
}int main()
{while(cin>>n){M=n*(n-1)/2;M=(M+1)/2;//中for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);int lb=-1,ub=a[n-1]-a[0]+1;while(ub-lb>1){int mid=(lb+ub)/2;if(C(mid))ub=mid;else lb=mid;//可行解再}cout<<lb<<endl;}
}
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>using namespace std;int a[100000+5];
int n,M;
bool C(int x)
{ int cnt=0;for(int i=0;i<n;i++)cnt+=upper_bound(a+i,a+n,a[i]+x)-(a+i)-1;return cnt<M;
}int main()
{while(cin>>n){M=n*(n-1)/2;M=(M+1)/2;//中for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);int lb=-1,ub=a[n-1]-a[0]+1;while(ub-lb>1){int mid=(lb+ub)/2;if(C(mid))lb=mid;else ub=mid;//可行解}cout<<ub<<endl;}
}