C# Program to Find the closest pair from two sorted arrays
Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array. We are given two arrays ar1[0…m-1] and ar2[0..n-1] and a number x, we need to find the pair ar1[i] + ar2[j] such that absolute value of (ar1[i] + ar2[j] – x) is minimum. Example:
Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 32 Output: 1 and 30 Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 50 Output: 7 and 40
C#
// C# program to find closest pair in // an array using System; class GFG { // ar1[0..m-1] and ar2[0..n-1] are two // given sorted arrays/ and x is given // number. This function prints the // pair from both arrays such that the // sum of the pair is closest to x. static void printClosest( int [] ar1, int [] ar2, int m, int n, int x) { // Initialize the diff between pair // sum and x. int diff = int .MaxValue; // res_l and res_r are result // indexes from ar1[] and ar2[] // respectively int res_l = 0, res_r = 0; // Start from left side of ar1[] // and right side of ar2[] int l = 0, r = n - 1; while (l < m && r >= 0) { // If this pair is closer to // x than the previously // found closest, then update // res_l, res_r and diff if (Math.Abs(ar1[l] + ar2[r] - x) < diff) { res_l = l; res_r = r; diff = Math.Abs(ar1[l] + ar2[r] - x); } // If sum of this pair is more // than x, move to smaller // side if (ar1[l] + ar2[r] > x) r--; else // move to the greater side l++; } // Print the result Console.Write( "The closest pair is [" + ar1[res_l] + ", " + ar2[res_r] + "]" ); } // Driver program to test above functions public static void Main() { int [] ar1 = { 1, 4, 5, 7 }; int [] ar2 = { 10, 20, 30, 40 }; int m = ar1.Length; int n = ar2.Length; int x = 38; printClosest(ar1, ar2, m, n, x); } } // This code is contributed by nitin mittal. |
Output:
The closest pair is [7, 30]
Time Complexity: O(m + n), where m and n represents the size of the given two arrays.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Please refer complete article on Find the closest pair from two sorted arrays for more details!
Contact Us