Dada una array ordenada y un número x, encuentre el par en la array cuya suma es más cercana a x

Dada una array ordenada y un número x, encuentre un par en una array cuya suma sea la más cercana a x.

Ejemplos:

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

Input: arr[] = {1, 3, 4, 7, 10}, x = 15
Output: 4 and 10

Una solución simple es considerar cada par y realizar un seguimiento del par más cercano (la diferencia absoluta entre la suma del par y x es mínima). Finalmente, imprima el par más cercano. La complejidad temporal de esta solución es O(n ² )

Una solución eficiente puede encontrar el par en tiempo O(n). La idea es similar al método 1 de esta publicación. El siguiente es un algoritmo detallado. 

1) Initialize a variable diff as infinite (Diff is used to store the 
   difference between pair and x).  We need to find the minimum diff.
2) Initialize two index variables l and r in the given sorted array.
       (a) Initialize first to the leftmost index:  l = 0
       (b) Initialize second  the rightmost index:  r = n-1
3) Loop while l < r.
       (a) If  abs(arr[l] + arr[r] - sum) < diff  then 
           update diff and result 
       (b) If(arr[l] + arr[r] <  sum )  then l++
       (c) Else r--    

A continuación se muestra la implementación del algoritmo anterior.

// Simple C++ program to find the pair with sum closest to a given no.
#include <bits/stdc++.h>
using namespace std;
 
// Prints the pair with sum closest to x
void printClosest(int arr[], int n, int x)
{
    int res_l, res_r;  // To store indexes of result pair
 
    // Initialize left and right indexes and difference between
    // pair sum and x
    int l = 0, r = n-1, diff = INT_MAX;
 
    // While there are elements between l and r
    while (r > l)
    {
       // Check if this pair is closer than the closest pair so far
       if (abs(arr[l] + arr[r] - x) < diff)
       {
           res_l = l;
           res_r = r;
           diff = abs(arr[l] + arr[r] - x);
       }
 
       // If this pair has more sum, move to smaller values.
       if (arr[l] + arr[r] > x)
           r--;
       else // Move to larger values
           l++;
    }
 
    cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r];
}
 
// Driver program to test above functions
int main()
{
    int arr[] =  {10, 22, 28, 29, 30, 40}, x = 54;
    int n = sizeof(arr)/sizeof(arr[0]);
    printClosest(arr, n, x);
    return 0;
}
// Code By Mayur Patil

// Java program to find pair with sum closest to x
import java.io.*;
import java.util.*;
import java.lang.Math;
 
class CloseSum {
     
    // Prints the pair with sum closest to x
    static void printClosest(int arr[], int n, int x)
    {
        int res_l=0, res_r=0;  // To store indexes of result pair
  
        // Initialize left and right indexes and difference between
        // pair sum and x
        int l = 0, r = n-1, diff = Integer.MAX_VALUE;
  
        // While there are elements between l and r
        while (r > l)
        {
            // Check if this pair is closer than the closest pair so far
            if (Math.abs(arr[l] + arr[r] - x) < diff)
            {
               res_l = l;
               res_r = r;
               diff = Math.abs(arr[l] + arr[r] - x);
            }
  
            // If this pair has more sum, move to smaller values.
            if (arr[l] + arr[r] > x)
               r--;
            else // Move to larger values
               l++;
        }
  
    System.out.println(" The closest pair is "+arr[res_l]+" and "+ arr[res_r]);
}
     
     
    // Driver program to test above function
    public static void main(String[] args)
    {
        int arr[] =  {10, 22, 28, 29, 30, 40}, x = 54;
        int n = arr.length;
        printClosest(arr, n, x);       
    }
}
/*This code is contributed by Devesh Agrawal*/

# Python3 program to find the pair
# with sum
# closest to a given no.
 
# A sufficiently large value greater
# than any
# element in the input array
MAX_VAL = 1000000000
 
 
#Prints the pair with sum closest to x
 
def printClosest(arr, n, x):
     
    # To store indexes of result pair
    res_l, res_r = 0, 0
     
    #Initialize left and right indexes
    # and difference between
    # pair sum and x
    l, r, diff = 0, n-1, MAX_VAL
     
    # While there are elements between l and r
    while r > l:
        # Check if this pair is closer than the
        # closest pair so far
        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:
        # If this pair has more sum, move to
        # smaller values.
            r -= 1
        else:
        # Move to larger values
            l += 1
         
    print('The closest pair is {} and {}'
         .format(arr[res_l], arr[res_r]))
 
 
# Driver code to test above
if __name__ == "__main__":
    arr = [10, 22, 28, 29, 30, 40]
    n = len(arr)
    x=54
    printClosest(arr, n, x)
 
# This code is contributed by Tuhin Patra

// C# program to find pair with sum closest to x
using System;
 
class GFG {
     
    // Prints the pair with sum closest to x
    static void printClosest(int []arr, int n, int x)
    {
         
        // To store indexes of result pair
        int res_l = 0, res_r = 0;
 
        // Initialize left and right indexes and
        // difference between pair sum and x
        int l = 0, r = n-1, diff = int.MaxValue;
 
        // While there are elements between l and r
        while (r > l)
        {
             
            // Check if this pair is closer than the
            // closest pair so far
            if (Math.Abs(arr[l] + arr[r] - x) < diff)
            {
                res_l = l;
                res_r = r;
                diff = Math.Abs(arr[l] + arr[r] - x);
            }
 
            // If this pair has more sum, move to
            // smaller values.
            if (arr[l] + arr[r] > x)
            r--;
            else // Move to larger values
            l++;
        }
     
        Console.Write(" The closest pair is " +
                 arr[res_l] + " and " + arr[res_r]);
    }
     
    // Driver program to test above function
    public static void Main()
    {
        int []arr = {10, 22, 28, 29, 30, 40};
        int x = 54;
        int n = arr.Length;
         
        printClosest(arr, n, x);    
    }
}
 
// This code is contributed by nitin mittal.

<?php
// Simple PHP program to find the
// pair with sum closest to a
// given no.
 
// Prints the pair with
// sum closest to x
function printClosest($arr, $n, $x)
{
     
    // To store indexes
    // of result pair
    $res_l;
    $res_r;
 
    // Initialize left and right
    // indexes and difference between
    // pair sum and x
    $l = 0;
    $r = $n - 1;
    $diff = PHP_INT_MAX;
 
    // While there are elements
    // between l and r
    while ($r > $l)
    {
         
        // Check if this pair is closer
        // than the closest pair so far
        if (abs($arr[$l] + $arr[$r] - $x) <
                                      $diff)
        {
            $res_l = $l;
            $res_r = $r;
            $diff = abs($arr[$l] + $arr[$r] - $x);
        }
     
        // If this pair has more sum,
        // move to smaller values.
        if ($arr[$l] + $arr[$r] > $x)
            $r--;
             
        // Move to larger values
        else
            $l++;
    }
 
    echo " The closest pair is "
         , $arr[$res_l] ," and "
         , $arr[$res_r];
}
 
    // Driver Code
    $arr = array(10, 22, 28, 29, 30, 40);
    $x = 54;
    $n = count($arr);
    printClosest($arr, $n, $x);
     
// This code is contributed by anuj_67.
?>

<script>
 
// JavaScript program to find pair
// with sum closest to x
 
     
    // Prints the pair with sum closest to x
    function printClosest(arr,n,x)
    {
    // To store indexes of result pair
        let res_l=0, res_r=0;
 
        // Initialize left and right indexes
        // and difference between
        // pair sum and x
        let l = 0, r = n-1, diff = Number.MAX_VALUE;
 
        // While there are elements
        // between l and r
        while (r > l)
        {
            // Check if this pair is closer
            // than the closest pair so far
            if (Math.abs(arr[l] +
                arr[r] - x) < diff)
            {
            res_l = l;
            res_r = r;
            diff = Math.abs(arr[l] + arr[r] - x);
            }
 
            // If this pair has more sum,
            // move to smaller values.
            if (arr[l] + arr[r] > x)
            r--;
            else // Move to larger values
            l++;
        }
 
    document.write(
    " The closest pair is "+arr[res_l]+" and "+ arr[res_r]
    );
}
     
     
    // Driver program to test above function
     
        let arr = [10, 22, 28, 29, 30, 40], x = 54;
        let n = arr.length;
        printClosest(arr, n, x);       
     
 
 
// This code is contributed by sravan kumar
 
</script>

 The closest pair is 22 and 30

Complejidad de tiempo: O(n) , donde n es la longitud de una array.
Espacio Auxiliar: O(1)