poj 3579、二分で答えを探して、更に二分で探します

題意:山の数をあげて、まずすべての2つの数の差を求める.これらの数の中位数を出力します.
理解:これらの数を直接列挙すると必ずタイムアウトします.C(n,2)個あるので、これは非常に大きいです.私は最初は私たちが要求した中位数の値を直接列挙しましたが、この数も非常に大きいです.それから他の人の考えを见て、私が依然として无邪気であることを発见します..このようにして、まず2点で答えを探して、1つの範囲内で2点で答えを列挙します;この答えが通じるかどうかを判断する.どう判断しますか?二分検索はこの値に基づいて、その範囲外の数であるいくつかより大きいものがあります.どうやって探しに行くのか分からないが、それは正しい...この値は前の差よりちょうど大きいので、この数が答えです.
コードは以下の通りです.コードはなぜ説明できるのか、もちろんシミュレーションも必要です.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <cmath>

using namespace std;

#define maxn 100100
#define x first
#define y second
#define ll long long
#define P pair<ll, ll>
#define INF 1e9

int a[maxn];

bool solve(int t, int m, int n)
{
    int count = 0;
    for (int i = 0; i < n; ++i)
    {
        count += n - (lower_bound(a, a + n, a[i] + t) - a);  //     ，         
    }
    if (count <= m)
    {
        return false;
    }
    else return true;
}

int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for (int i = 0; i < n; ++i)
        {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);

        ll m = n * (n - 1) / 4;
        int lb = 0, rb = a[n - 1]; //           
        while(rb - lb > 1)  //    
        {
            int mid = (lb + rb) / 2;
            if (solve(mid, m, n))
            {
                lb = mid;
            }
            else
            {
                rb = mid;
            }
        }
        printf("%d
", lb);
    }

    return 0;
}