Find the closest pair from two sorted arrays in c++

Suppose we have two sorted arrays and a number x, we have to find the pair whose sum is closest to x. And the pair has an element from each array. We have two arrays A1 [0..m-1] and A2 [0..n-1], and another value x. We have to find the pair A1[i] + A2[j] such that absolute value of (A1[i] + A2[j] – x) is minimum. So if A1 = [1, 4, 5, 7], and A2 = [10, 20, 30, 40], and x = 32, then output will be 1 and 30.

We will start from left of A1 and right from A2, then follow these steps to find such pair

• Initialize diff, this will hold the difference between pair and x
• Initialize two pointer left := 0 and right := n – 1
• While left <= m and right >= 0, do
  • if |A1[left] + A2[right] – sum| < diff, then
    • update diff and result
  • if (A1[left] + A2[right]) < sum, then
    • increase left by 1
  • otherwise
    • Decrease right by 1
• Display the result

Example

#include<iostream> #include<cmath> using namespace std; void findClosestPair(int A1[], int A2[], int m, int n, int x) {    int diff = INT_MAX;    int left_res, right_res;    int left = 0, right = n-1;    while (left<m && right>=0) {       if (abs(A1[left] + A2[right] - x) < diff) {          left_res = left;          right_res = right;          diff = abs(A1[left] + A2[right] - x);       }       if (A1[left] + A2[right] > x)       right--;       else       left++;    }    cout << "The closest pair is [" << A1[left_res] << ", "<< A2[right_res] << "]"; } int main() {    int ar1[] = {1, 4, 5, 7};    int ar2[] = {10, 20, 30, 40};    int m = sizeof(ar1)/sizeof(ar1[0]);    int n = sizeof(ar2)/sizeof(ar2[0]);    int x = 32;    findClosestPair(ar1, ar2, m, n, x); }

Output

The closest pair is [1, 30]