{"id":25361,"date":"2017-10-15T17:18:32","date_gmt":"2017-10-15T11:48:32","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25361"},"modified":"2017-10-15T17:18:32","modified_gmt":"2017-10-15T11:48:32","slug":"given-sorted-array-number-x-find-pair-array-whose-sum-closest-x-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/given-sorted-array-number-x-find-pair-array-whose-sum-closest-x-2\/","title":{"rendered":"C programming &#8211; Given a sorted array and a number x, find the pair in array whose sum is closest to x"},"content":{"rendered":"<p>Given a sorted array and a number x, find a pair in array whose sum is closest to x.<span id=\"more-142564\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54\r\nOutput: 22 and 30\r\n\r\nInput: arr[] = {1, 3, 4, 7, 10}, x = 15\r\nOutput: 4 and 10\r\n<\/pre>\n<p>A simple solution is to consider every pair and keep track of closest pair (absolute difference between pair sum and x is minimum). Finally print the closest pair. Time complexity of this solution is O(n<sup>2<\/sup>)<\/p>\n<p>An efficient solution can find the pair in O(n) time. The idea is similar to method 2 of this post. Following is detailed algorithm.<\/p>\n<pre>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:  l = 0\r\n       (b) Initialize second  the rightmost index:  r = n-1\r\n3) Loop while l &lt; r.\r\n       (a) If  abs(arr[l] + arr[r] - sum) &lt; diff  then \r\n           update diff and result \r\n       (b) Else if(arr[l] + arr[r] &lt;  sum )  then l++\r\n       (c) Else r--<\/pre>\n[ad type=&#8221;banner&#8221;]\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>C programming &#8211; Given a sorted array and a number x, find the pair in array whose sum is closest to x &#8211; Searching and sorting.- Given a sorted array. find a pair in array whose sum is closest to x.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[82927,1,71670,83512],"tags":[71128,71222,72388,71133,71893,72390,72302,70892,71121,71135,71134,71141,71131,71130,72392,72389,71144,70895,70017,72386,71160,71158,70075,70914,70046,71714,71265,70272,72695,70016,70548,72387,72385,72299,71695,70020,71161,72391,71149,72384,70967,72303,71156,71219,71142,72190,72185],"class_list":["post-25361","post","type-post","status-publish","format-standard","hentry","category-c-programming-2","category-coding","category-searching-and-sorting","category-sorted-array","tag-algorithm-for-bubble-sort","tag-algorithm-for-insertion-sort","tag-algorithm-for-sorting","tag-algorithm-of-bubble-sort","tag-algorithm-sort","tag-array-sorting-algorithm","tag-best-sorting","tag-best-sorting-algorithm","tag-bubble-sort-algorithm","tag-bubble-sort-algorithm-in-data-structure","tag-bubble-sort-algorithm-with-example","tag-bubble-sort-animation","tag-bubble-sort-code","tag-bubble-sort-in-data-structure","tag-c-sorting-algorithms","tag-common-sorting-algorithms","tag-different-sorting-algorithms","tag-fastest-sorting-algorithm","tag-insertion-sort-algorithm","tag-insertion-sort-animation","tag-insertion-sort-in-data-structure","tag-java-sort","tag-linear-sort","tag-most-efficient-sorting-algorithm","tag-quicksort","tag-quicksort-algorithm-in-data-structure","tag-quicksort-example","tag-search-algorithms","tag-search-in-an-almost-sorted-array","tag-selection-sort-algorithm","tag-selection-sort-in-data-structure","tag-simple-sorting-algorithm","tag-sort-algorithm-c","tag-sort-c","tag-sorted","tag-sorting-algorithms","tag-sorting-algorithms-comparison","tag-sorting-algorithms-examples","tag-sorting-algorithms-in-data-structures","tag-sorting-algorithms-in-data-structures-with-examples","tag-sorting-algorithms-java","tag-sorting-algorithms-visualized","tag-sorting-algorithms-with-examples","tag-sorting-in-c","tag-sorting-in-data-structure","tag-sorting-methods","tag-sortings"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25361","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=25361"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25361\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}