Binary Search with 3 pointers


#1

`
vector search(const vector &A,int target){
int n = A.size();
vector v(2);
int ind = upper_bound(A.begin(),A.end(),target)-A.begin();
ind -= 1;
if(ind < 0){
//only upper bound
v[0] = INT_MIN;
v[1] = A[ind+1];
}
else if(ind==n-1){
v[0] = A[ind];
v[1] = INT_MAX;
}
else{
if(A[ind] == target){
v[0] = v[1] = target;
}
else{
v[0] = A[ind];
v[1] = A[ind+1];
}
}
return v;
}
int Solution::minimize(const vector &A, const vector &B, const vector &C) {
int b_size = B.size();
long long ans = INT64_MAX;
for(int i=0; i<b_size; i++){
int target = B[i];
//check in A
vector a = search(A,target);

    //check in C
    vector<int> c = search(C,target);
    //get maxx_diff
    long long diff1 = max(abs(B[i]-a[1]),abs(B[i]-c[1]));
    long long diff2 = max(abs(B[i]-a[0]),abs(B[i]-c[0]));
    long long diff3 = abs(a[0]-c[1]);
    long long diff4 = abs(a[1]-c[0]);
    
    ans = min(ans,min(min(diff1,diff2),min(diff3,diff4)));
    //minimise that
}
return (int)ans;

}

`