C++ में दो सॉर्टेड ऐरे से निकटतम पेयर ढूंढना

मान लें हमारे पास दो सॉर्टेड ऐरे और एक संख्या x है, हमें वह पेयर ढूंढना है जिसका योग x के निकटतम हो। और पेयर में प्रत्येक ऐरे से एक तत्व हो। हमारे पास दो ऐरे A1[0..m-1] और A2[0..n-1] हैं, और एक अन्य मान x है। हमें पेयर A1[i] + A2[j] ढूंढना है जैसे कि (A1[i] + A2[j] - x) का निरपेक्ष मान न्यूनतम हो। इसलिए यदि A1 = [1, 4, 5, 7], और A2 = [10, 20, 30, 40], और x = 32, तो आउटपुट 1 और 30 होगा।

हम A1 के बाएं से और A2 के दाएं से शुरू करेंगे, फिर ऐसे पेयर को ढूंढने के लिए इन चरणों का पालन करेंगे:

diff प्रारंभ करें, यह पेयर और x के बीच का अंतर रखेगा।
दो पॉइंटर प्रारंभ करें left := 0 और right := n - 1।
जब तक left <= m और right >= 0, करें:
- यदि |A1[left] + A2[right] - sum| < diff, तो:
  - diff और परिणाम अपडेट करें।
- यदि (A1[left] + A2[right]) < sum, तो:
  - left को 1 से बढ़ाएं।
- अन्यथा:
  - right को 1 से घटाएं।
परिणाम प्रदर्शित करें।

उदाहरण

#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);
}

आउटपुट

The closest pair is [1, 30]