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

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