Programa Php para encontrar un par con la diferencia dada

Dada una array no ordenada y un número n, encuentre si existe un par de elementos en la array cuya diferencia es n. 
Ejemplos: 
 

Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78
Output: Pair Found: (2, 80)

Input: arr[] = {90, 70, 20, 80, 50}, n = 45
Output: No Such Pair

El método más simple es ejecutar dos bucles, el bucle exterior selecciona el primer elemento (elemento más pequeño) y el bucle interior busca el elemento seleccionado por el bucle exterior más n. La complejidad temporal de este método es O(n^2).
Podemos usar la clasificación y la búsqueda binaria para mejorar la complejidad del tiempo a O (nLogn). El primer paso es ordenar la array en orden ascendente. Una vez que la array esté ordenada, recorra la array de izquierda a derecha, y para cada elemento arr[i], busque binariamente arr[i] + n en arr[i+1..n-1]. Si se encuentra el elemento, devuelve el par. 
Tanto el primer como el segundo paso toman O (nLogn). Entonces, la complejidad general es O (nLogn). 
El segundo paso del algoritmo anterior se puede mejorar a O(n). El primer paso sigue siendo el mismo. La idea para el segundo paso es tomar dos variables de índice i y j, inicializarlas como 0 y 1 respectivamente. Ahora ejecute un bucle lineal. Si arr[j] – arr[i] es más pequeño que n, debemos buscar un arr[j] mayor, por lo tanto, incremente j. Si arr[j] – arr[i] es mayor que n, debemos buscar un arr[i] mayor, por lo tanto, incremente i. Gracias a Aashish Barnwal por sugerir este enfoque. 
El siguiente código es solo para el segundo paso del algoritmo, asume que la array ya está ordenada. 
 

<?php 
// PHP program to find a pair with
// the given difference
  
// The function assumes that the 
// array is sorted 
function findPair(&$arr, $size, $n)
{
    // Initialize positions of 
    // two elements
    $i = 0; 
    $j = 1;
  
    // Search for a pair
    while ($i < $size && $j < $size)
    {
        if ($i != $j && $arr[$j] - 
                        $arr[$i] == $n)
        {
            echo "Pair Found: " . "(" . 
                  $arr[$i] . ", " . $arr[$j] . ")";
            return true;
        }
        else if ($arr[$j] - $arr[$i] < $n)
            $j++;
        else
            $i++;
    }
  
    echo "No such pair";
    return false;
}
  
// Driver Code
$arr = array(1, 8, 30, 40, 100);
$size = sizeof($arr);
$n = 60;
findPair($arr, $size, $n);
  
// This code is contributed 
// by ChitraNayal
?>

Producción:  

Pair Found: (40, 100)

Hashing también se puede utilizar para resolver este problema. Cree una tabla hash vacía HT. Recorra la array, use los elementos de la array como claves hash e ingréselos en HT. Atraviese la array nuevamente y busque el valor n + arr[i] en HT. 
 

¡ Consulte el artículo completo sobre Encuentre un par con la diferencia dada para obtener más detalles!