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 से दाएं से शुरू करेंगे, फिर ऐसी जोड़ी को खोजने के लिए इन चरणों का पालन करें

• initialize diff, इससे युग्म और x के बीच का अंतर बना रहेगा
• दो पॉइंटर को इनिशियलाइज़ करें बाएँ:=0 और दाएँ:=n – 1
• बाएं <=मीटर और दाएं>=0, करते समय
  • अगर |A1[बाएं] + A2 [दाएं] - योग|
  • अद्यतन अंतर और परिणाम
• अगर (A1[बाएं] + A2 [दाएं]) <योग, तो
  • बाएं 1 से बढ़ाएं
• अन्यथा
  • दाएं 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]