Given a sorted array and a number x, find a pair in array whose sum is closest to x.

Examples:

Input: arr[] = {10, 22, 28, 29, 32, 40}, x = 54

Output: 22 and 32

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(n2)

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.

#include <iostream> #include <climits> #include <cstdlib> using namespace std; // Prints the pair with sum cloest to x void printClosest(int arr[], int n, int x) { int res_l, res_r; int l = 0, r = n-1, diff = INT_MAX; while (r > l) { if (abs(arr[l] + arr[r] - x) < diff) { res_l = l; res_r = r; diff = abs(arr[l] + arr[r] - x); } if (arr[l] + arr[r] > x) r--; else l++; } cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r]; } int main() { int arr[] = {10, 22, 28, 29, 32, 40}, x = 54; int n = sizeof(arr)/sizeof(arr[0]); printClosest(arr, n, x); return 0; } See Running code at http://ideone.com/q3F4OQ