PHP Program to Find the closest pair from two sorted arrays

0 0 2 minutes read

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.
We are given two arrays ar1[0…m-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] – x) is minimum.
Example:

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 32      
Output:  1 and 30

Input:  ar1[] = {1, 4, 5, 7};
        ar2[] = {10, 20, 30, 40};
        x = 50      
Output:  7 and 40

PHP

<?php
// PHP program to find the pair 
// from two sorted arrays such
// that the sum of pair is 
// closest to a given number x
 
// ar1[0..m-1] and ar2[0..n-1] 
// are two given sorted arrays
// and x is given number. This
// function prints the pair from
// both arrays such that the sum
// of the pair is closest to x.
function printClosest($ar1, $ar2,
                      $m, $n, $x)
{
     
    // Initialize the diff between
    // pair sum and x.
    $diff = PHP_INT_MAX;
 
    // res_l and res_r are result
    // indexes from ar1[] and ar2[]
    // respectively
    $res_l; 
    $res_r;
 
    // Start from left side of 
    // ar1[] and right side of ar2[]
    $l = 0;
    $r = $n - 1;
    while ($l < $m and $r >= 0)
    {
         
        // If this pair is closer to 
        // x than the previously
        // found closest, then 
        // update res_l, res_r and
        // diff
        if (abs($ar1[$l] + $ar2[$r] - 
                       $x) < $diff)
        {
            $res_l = $l;
            $res_r = $r;
            $diff = abs($ar1[$l] +
                    $ar2[$r] - $x);
        }
     
        // If sum of this pair is 
        // more than x, move to smaller
        // side
        if ($ar1[$l] + $ar2[$r] > $x)
            $r--;
             
        // move to the greater side
        else
            $l++;
    }
 
    // Print the result
    echo "The closest pair is [", $ar1[$res_l], ", ", $ar2[$res_r], "] \n";
}
 
    // Driver Code
    $ar1 = array(1, 4, 5, 7);
    $ar2 = array(10, 20, 30, 40);
    $m = count($ar1);
    $n = count($ar2);
    $x = 38;
    printClosest($ar1, $ar2, $m, $n, $x);
 
// This code is contributed by anuj_67.
?>