{"id":25316,"date":"2017-10-15T17:04:50","date_gmt":"2017-10-15T11:34:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25316"},"modified":"2017-10-15T17:04:50","modified_gmt":"2017-10-15T11:34:50","slug":"find-closest-pair-two-sorted-arrays","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/find-closest-pair-two-sorted-arrays\/","title":{"rendered":"JAVA programming-Find the closest pair from two sorted arrays"},"content":{"rendered":"

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<\/strong>.<\/span><\/p>\n

We are given two arrays ar1[0\u2026m-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] \u2013 x) is minimum.<\/p>\n

Example:<\/p>\n

Input:  ar1[] = {1, 4, 5, 7};\r\n        ar2[] = {10, 20, 30, 40};\r\n        x = 32      \r\nOutput:  1 and 30\r\n\r\nInput:  ar1[] = {1, 4, 5, 7};\r\n        ar2[] = {10, 20, 30, 40};\r\n        x = 50      \r\nOutput:  7 and 40\r\n<\/pre>\n
We strongly recommend to minimize your browser and try this yourself first.<\/strong><\/p>\n
A Simple Solution<\/strong> is to run two loops. The outer loop considers every element of first array and inner loop checks for the pair in second array. We keep track of minimum difference between ar1[i] + ar2[j] and x.<\/p>\n
We can do it in O(n) time <\/strong>using following steps.
\n1) Merge given two arrays into an auxiliary array of size m+n using merge process of merge sort<\/a>. While merging keep another boolean array of size m+n to indicate whether the current element in merged array is from ar1[] or ar2[].<\/p>\n
2) Consider the merged array and use the linear time algorithm to find the pair with sum closest to x<\/a>. One extra thing we need to consider only those pairs which have one element from ar1[] and other from ar2[], we use the boolean array for this purpose.<\/p>\n[ad type=”banner”]\n
Can we do it in a single pass and O(1) extra space?<\/strong>
\nThe idea is to start from left side of one array and right side of another array, and use the algorithm same as step 2 of above approach. Following is detailed algorithm.<\/p>\n
1) Initialize a variable diff as infinite (Diff is used to store the \r\n   difference between pair and x).  We need to find the minimum diff.\r\n2) Initialize two index variables l and r in the given sorted array.\r\n       (a) Initialize first to the leftmost index in ar1:  l = 0\r\n       (b) Initialize second  the rightmost index in ar2:  r = n-1\r\n3) Loop while l < m and r >= 0\r\n       (a) If  abs(ar1[l] + ar2[r] - sum) < diff  then \r\n           update diff and result \r\n       (b) Else if(ar1[l] + ar2[r] <  sum )  then l++\r\n       (c) Else r--    \r\n4) Print the result.<\/pre>\n
Following is JAVA implementation of this approach.<\/p>\n
 
 JAVA<\/span> <\/div> 
\/\/ Java program to find closest pair in an arrayclass ClosestPair{    \/\/ 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.    void printClosest(int ar1[], int ar2[], int m, int n, int x)    {        \/\/ Initialize the diff between pair sum and x.        int diff = Integer.MAX_VALUE;         \/\/ 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        System.out.print("The closest pair is [" + ar1[res_l] +                         ", " + ar2[res_r] + "]");    }     \/\/ Driver program to test above functions    public static void main(String args[])    {        ClosestPair ob = new ClosestPair();        int ar1[] = {1, 4, 5, 7};        int ar2[] = {10, 20, 30, 40};        int m = ar1.length;        int n = ar2.length;        int x = 38;        ob.printClosest(ar1, ar2, m, n, x);    }}<\/code><\/pre> <\/div>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Find the closest pair from two sorted arrays – Searching and Sorting – 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.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83519,71670,83512],"tags":[72937,72963,72927,72931,72949,72957,72969,72922,72920,72925,72944,72972,72933,72943,72926,72923,72934,72951,72967,72924,72954,72962,72945,72929,72921,72946,72956,70756,72928,72953,72964,72941,72936,72968,72947,72948,72919,72939,72959,72974,72952,72950,72971,72955,72970,72938,72930,72932,72940,72973,72935,72101,72965,72960,72942,72966,70402,72958,72961],"class_list":["post-25316","post","type-post","status-publish","format-standard","hentry","category-closest-pair","category-searching-and-sorting","category-sorted-array","tag-algorithm-design-kleinberg-pdf","tag-bentley-1980","tag-c-pair","tag-closer","tag-closest-h-and-m","tag-closest-javascript","tag-closest-one","tag-closest-pair","tag-closest-pair-algorithm","tag-closest-pair-algorithm-divide-and-conquer","tag-closest-pair-algorithm-pseudocode","tag-closest-pair-of-points","tag-closest-pair-of-points-algorithm","tag-closest-pair-of-points-divide-and-conquer-algorithm","tag-closest-pair-of-points-problem","tag-closest-pair-problem","tag-closest-pair-problem-algorithm","tag-closest-point","tag-closest-point-algorithm","tag-closests","tag-conquer-and-divide","tag-conquer-points","tag-conquest-2","tag-convex-hull-algorithm","tag-coord-sets","tag-define-closer","tag-divide-and-concur","tag-divide-and-conquer","tag-divide-and-conquer-algorithm","tag-divide-and-conquer-algorithm-examples","tag-divide-and-conquer-examples","tag-divide-and-conquer-meaning","tag-divide-and-conquer-strategy","tag-divide-conquer","tag-divide-in-python","tag-find-the-closest","tag-find-the-closest-pair-from-two-sorted-arrays","tag-find-the-distance-between-each-pair-of-points","tag-find-the-distance-between-the-pair-of-points","tag-find-the-distance-from-the-point-to-the-given-plane","tag-finding-the-closest-pair-of-points","tag-force-pair","tag-infiniti-cars-wiki","tag-mastering-algorithms-with-c-pdf","tag-matlab-find-closest-value","tag-multiplication-algorithm","tag-n-log-n","tag-python-division","tag-python-pair","tag-shortest-distance-between-two-cities","tag-shortest-distance-between-two-points","tag-sorting-algorithms-pdf","tag-sweep-line","tag-sweep-line-algorithm","tag-the-closest-one","tag-the-closest-pair-problem","tag-the-master-algorithm-pdf","tag-the-shortest-distance-between-two-points","tag-what-is-the-shortest-distance-between-two-points"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25316"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25316\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}