POJ.3579 Median

1.Problem
http://poj.org/problem?id=3579

2.Idea
Binary Search + Lower_Bound

3.Source

 int N;  
 ll M;  
 int x[100005];  
 bool C(int f)  
 {  
      ll cnt = 0;  
      for (int i = 0; i < N; i++) {  
           cnt += lower_bound(x + i + 1, x + N, x[i] + f) - (x + (i + 1));  
      }  
      return cnt < M;  
 }  
 void solve()  
 {  
      sort(x, x + N);  
      M = (ll)N * (N - 1) / 2;  
      if (M % 2) M = M / 2 + 1;  
      else   M = M / 2;  
      int l = 0;  
      int r = 1000000010;  
      while(r - l > 1) {  
           int m = (l + r) / 2;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      printf("%d\n", l);  
 }  
 int main()  
 {  
      while (scanf("%d", &N) > 0) {  
           for (int i = 0; i < N; i++) scanf("%d", &x[i]);  
           solve();  
      }  
      return 0;  
 }