Median (two point answer + two point search)

Median

The question :

Yes N It's an integer , Calculate the difference between two different integers , Then find the median of the difference .

Ideas :

Two points answer + Two points search

The subject data range is xi <= 1e9,N <= 1e5; If direct violence 1e10 The complexity of will explode ;1e9 Data needs to be longlong Handle ;

Possible values of median of binary enumeration , Then find the number that meets the condition in two ;

The number we are looking for here is the number of numbers smaller than the median , There are n * (n - 1) / 2 Number Then the median of even numbers is n * (n - 1) / 4 , Odd number is n * (n - 1) / 4 + 1;

Directly add the median to each value , then upper_bound Count how many numbers are smaller than the median value , Finally, see whether half the number is satisfied

Choose the big and the small , The rational use of lower_bound And pay attention to which side to search

AC Code :
Take large

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
ll n, m;

bool check(int x){
    ll sum = 0;
    for(int i = 0;i < n;i ++){
        int pos = n - (upper_bound(a,a + n,a[i] + x) - a);
        sum += pos;
    }
    return sum <= m;
}

int main(){
    while(~scanf("%d",&n)){
        for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
        sort(a,a + n);
        m = n * (n - 1) / 4;
//        if(m & 1) m = m / 2;
//        else m = m / 2;
        int l = -1,r = a[n - 1] - a[0];
        while(l < r){
            int mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n",l);
    }
    return 0;
}

Take the small one

# include <iostream>
# include<cstdio>
# include <algorithm>
 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
ll n, m;
 
bool check(int x){
    ll sum = 0;
    for(int i=0; i<n-1; ++i){ // How many ratios are there x Small 
        int pos = upper_bound(a+i, a+n, a[i]+x)-a;
        sum += pos - i - 1;
        if(sum >= m)
            return true;
    }
    return false;
}

int main(){
    while(~scanf("%lld",&n)){
        for(int i=0; i<n; ++i)
            scanf("%d",&a[i]);
        ll tmp = n*(n-1)>>1;
        if(tmp&1)
            m = (tmp>>1)+1;
        else
            m = tmp>>1;
        sort(a, a+n);
        int l=0, r=a[n-1]-a[0], mid;
        while(l<r)
        {
            int mid = (l + r)>>1;
            if(check(mid))
                r = mid;
            else
                l = mid+1;
        }
        printf("%d\n",r);
    }
    return 0;
}