Sherlock and MiniMax

• Time : O(nlogn)
• Space : O(1)

int helper(vector<int>& A, int k) {
    auto lb = lower_bound(begin(A), end(A), k);
    if(lb == end(A)) {
        return k - A.back();
    } else if(lb == begin(A)) {
        return A[0] - k;
    } else {
        return min(abs(*lb - k), abs(*(prev(lb)) - k));
    }
}

int sherlockAndMinimax(vector<int> A, int p, int q) {
    sort(begin(A), end(A));
    int pmi = helper(A, p), qmi = helper(A, q);
    int mi = max(qmi, pmi);
    int res = qmi > pmi ? q : p;
    
    for(int i = 0; i < A.size() - 1; i++) {
        int d = (A[i + 1] - A[i]) / 2;
        int target = A[i] + d;
        if(p <= target and target <= q) {
            if(d == mi) {
                res = min(res, target);
            } else if(d > mi) {
                mi = d;
                res = target;
            }
        }
    }
    
    return res;
}