Sherlock and MiniMax

This is a problem from HackerRank, is not a complex problem but i think the solution is interesting for the way approach the problem. I will present here at first two versions of the algorithm, one have O(n^2) complexity and the second O(nlogn). I have also a O(n) solution which i need to analyze better, then i will post it as well..

But first thing first, the problem statement (LINK):

Watson gives Sherlock an array A1,A2…AN.
He asks him to find an integer M between P and Q(both inclusive), such that, min {|Ai-M|, 1 ≤ i ≤ N} is maximised. If there are multiple solutions, print the smallest one.

Input Format
The first line contains N. The next line contains space separated N integers, and denote the array A. The third line contains two space separated integers denoting P and Q.

Output Format
In one line, print the required answer.

Constraints
1 ≤ N ≤ 102
1 ≤ Ai ≤ 109
1 ≤ P ≤ Q ≤ 109

Sample Input

3 5 8 14 4 9 

Sample Output

4

Clearly the solution must be P, Q or one of the deltas betweent the values of the array, we have n-1 delta and we need to check for each of them the min distance for all the n values, which give us an asymptotic complexity of O(n^2), here’s the code:

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;

ll p,q,b,n,ans{1e9};
vector<ll> d(n);

void solve(ll m)
{
    if(m>=p&&m<=q){
        ll t{1e9};
        for(int i{0};i<n;i++)
            t = min(t, abs(d[i]-m));
        if(t > b || (t==b && m<ans)){
            b = t;
            ans = m;
        }
    }
}

int main() {
    cin >> n;
    d.resize(n);
    for(int i{0};i<n;i++)
        cin >> d[i];
    sort(d.begin(),d.end());
    cin >> p >> q;
    solve(p);
    solve(q);
    for(int i{1};i<n;i++)
        solve((d[i]+d[i-1])/2);
    cout<<ans<<endl;
    return 0;
}

This code is good enough to clear the testcases provided for the problem, but we can do much better observing that is possible to seek for the solution just searching in the whole range of possible values 1…1e9 the value for which the minmax is satisfied, this can be done with a binary search:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using ll = long long;

ll p,q,b,n;
vector<ll> d(n);

ll solve(ll m)
{
    ll tp = p, tq = q;
    for(int i{0};i<n;i++)
    {
        if(d[i]-m<tp){
            tp = max(tp, d[i] + m);
        }
    }
    if(tp>tq) return -1;
    return tp;
}

int main() {
    cin >> n;
    d.resize(n);
    for(int i{0};i<n;i++)
        cin >> d[i];
    sort(d.begin(),d.end());
    cin >> p >> q;
    ll l{1}, r{1e9}, m;
    while(l<r)
    {
        m = l + r + 1;
        m /= 2;
        if(solve(m)!=-1)
            l = m;
        else
            r = m - 1;
    }
    cout<<solve(l)<<endl;
    return 0;
}

Basically this code will shrink the range of possible solutions until just one is left. The code for the O(n) implementation came from a friend of mine, i will not modify the code to match the way i link it to be formatted &c but i will leave it exacly as Lukasz give it to me:

#include <cstdio>
#include <algorithm>

using namespace std;

int t[10000];

int solve(int p, int q, int n)
{
	if (q <= t[0]) return p;
	if (p >= t[n - 1]) return q;

	pair<int, int> best = {0, 0};
	if (p <= t[0]) best = {t[0] - p, p};
	for (int i = 0; i + 1 < n; i++)
	{
		int s = t[i] + t[i + 1];
		s /= 2;
		if (p <= s && s <= q)
		{
			if (s - t[i] > best.first) best = {s - t[i], s};
		}
		else if (t[i] <= p && p <= t[i + 1])
		{
			if (p < s) if (p - t[i] > best.first) best = {p - t[i], p};
			if (p > s) if (t[i + 1] - p > best.first) best = {t[i + 1] - p, p};
		}
		else if (t[i] <= q && q <= t[i + 1])
		{
			if (q < s) if (q - t[i] > best.first) best = {q - t[i], q};
			if (q > s) if (t[i + 1] - q > best.first) best = {t[i + 1] - q, q};
		}
	}
	if (q >= t[n - 1]) if (q - t[n - 1] > best.first) best = {q - t[n - 1], q};
	return best.second;
}

int main()
{
	int n, p, q;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", t + i);
	}
	scanf("%d%d", &p, &q);
	sort(t, t + n);
	printf("%dn", solve(p, q, n));

	return 0;

}

Well, the code is O(n) if we ignore the O(nlogn) complexity of the sort operation But we do of course! The cleaver idea behind this solution is just to seek for the sweet point picking s,p or q depending of the closest distance from the give point to one of the two possible borders for each delta (t[n], and t[n+1]). Thanks to Lukasz for this idea