{"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=\u201dbanner\u201d]\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[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20to%20find%20closest%20pair%20in%20an%20array%0Aclass%20ClosestPair%0A%7B%0A%20%20%20%20%2F%2F%20ar1%5B0..m-1%5D%20and%20ar2%5B0..n-1%5D%20are%20two%20given%20sorted%0A%20%20%20%20%2F%2F%20arrays%2F%20and%20x%20is%20given%20number.%20This%20function%20prints%0A%20%20%20%20%2F%2F%20the%20pair%20from%20both%20arrays%20such%20that%20the%20sum%20of%20the%0A%20%20%20%20%2F%2F%20pair%20is%20closest%20to%20x.%0A%20%20%20%20void%20printClosest(int%20ar1%5B%5D%2C%20int%20ar2%5B%5D%2C%20int%20m%2C%20int%20n%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20the%20diff%20between%20pair%20sum%20and%20x.%0A%20%20%20%20%20%20%20%20int%20diff%20%3D%20Integer.MAX_VALUE%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20res_l%20and%20res_r%20are%20result%20indexes%20from%20ar1%5B%5D%20and%20ar2%5B%5D%0A%20%20%20%20%20%20%20%20%2F%2F%20respectively%0A%20%20%20%20%20%20%20%20int%20res_l%20%3D%200%2C%20res_r%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Start%20from%20left%20side%20of%20ar1%5B%5D%20and%20right%20side%20of%20ar2%5B%5D%0A%20%20%20%20%20%20%20%20int%20l%20%3D%200%2C%20r%20%3D%20n-1%3B%0A%20%20%20%20%20%20%20%20while%20(l%3Cm%20%26%26%20r%3E%3D0)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20this%20pair%20is%20closer%20to%20x%20than%20the%20previously%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20found%20closest%2C%20then%20update%20res_l%2C%20res_r%20and%20diff%0A%20%20%20%20%20%20%20%20%20%20%20if%20(Math.abs(ar1%5Bl%5D%20%2B%20ar2%5Br%5D%20-%20x)%20%3C%20diff)%0A%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res_l%20%3D%20l%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res_r%20%3D%20r%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20diff%20%3D%20Math.abs(ar1%5Bl%5D%20%2B%20ar2%5Br%5D%20-%20x)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20sum%20of%20this%20pair%20is%20more%20than%20x%2C%20move%20to%20smaller%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20side%0A%20%20%20%20%20%20%20%20%20%20%20if%20(ar1%5Bl%5D%20%2B%20ar2%5Br%5D%20%3E%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20r\u2013%3B%0A%20%20%20%20%20%20%20%20%20%20%20else%20%20%2F%2F%20move%20to%20the%20greater%20side%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20l%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20the%20result%0A%20%20%20%20%20%20%20%20System.out.print(%22The%20closest%20pair%20is%20%5B%22%20%2B%20ar1%5Bres_l%5D%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%2C%20%22%20%2B%20ar2%5Bres_r%5D%20%2B%20%22%5D%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20program%20to%20test%20above%20functions%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20ClosestPair%20ob%20%3D%20new%20ClosestPair()%3B%0A%20%20%20%20%20%20%20%20int%20ar1%5B%5D%20%3D%20%7B1%2C%204%2C%205%2C%207%7D%3B%0A%20%20%20%20%20%20%20%20int%20ar2%5B%5D%20%3D%20%7B10%2C%2020%2C%2030%2C%2040%7D%3B%0A%20%20%20%20%20%20%20%20int%20m%20%3D%20ar1.length%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20ar2.length%3B%0A%20%20%20%20%20%20%20%20int%20x%20%3D%2038%3B%0A%20%20%20%20%20%20%20%20ob.printClosest(ar1%2C%20ar2%2C%20m%2C%20n%2C%20x)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201dJAVA\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\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}]}}