How can I determine two numbers that are more close than others in an array

Question

I have this array:

$arr = array (20, 1, 5, 10, 7, 16);

I would like to get 5 and 7. Because these are more close to each other than other items. In other word the difference between them is the lowest number:

7 - 5 = 2 // 2 is lowest number as the difference between all array's items

How can I do that?

---

$keep = $arr[0];
$diff = $arr[1] - $arr[0];
foreach ($arr as $item) {
    if ( ($keep - $item) < $diff && $keep != $item ) {
        $diff = $item;
    }
}

My code is incomplete, Because it just compares first item with other items.

Answer 1

Explanation

So to get the two numbers in an array which are the closest to each other you have to compare each value with each other value. But you don't have to compare them with themselves and to the previous ones which you already compared.

To calculate how many comparisons you have to do you can use the binomial coefficient:

(n)            n!
(k)   →   ─────────────
          k! * (n - k)!

_{Where n is the total amount of elements and k how many you pick}

And in your example this would mean:

n = 6 //Array elements
k = 2 //Two values which you compare

     6!                  720
─────────────   →   ─────────────   = 15 comparison
2! * (6 - 2)!          2  *  24

Visualized

20 , 1 , 5 , 10 , 7 , 16  //Array values
↓    ↑   ↑   ↑    ↑   ↑
└────┴───┴───┴────┴───┘  //20 compared to all values, except itself
     ↓   ↑   ↑    ↑   ↑
     └───┴───┴────┴───┘  //1  compared to all values, except itself + [20]
         ↓   ↑    ↑   ↑
         └───┴────┴───┘  //5  compared to all values, except itself + [20, 1]
             ↓    ↑   ↑
             └────┴───┘  //10 compared to all values, except itself + [20, 1, 5]
                  ↓   ↑
                  └───┘  //7  compared to all values, except itself + [20, 1, 5, 10]

                         //16 compared to all values, except itself + [20, 1, 5, 10, 7]

Now to do this in code we need 2 loops to loop over the entire array for each value of the first loop. But as we already said we can ignore the value itself and the previous values, so for this we use 2 for loops and set the key, for the inner loop, to be the outer key + 1.

for($key = 0, $length = count($arr); $key < $length; $key++){          
    for($innerKey = $key + 1; $innerKey < $length; $innerKey++){
      //↑ Skipping the previous values and the value itself    
    }               
}

In the inner loop itself we just need to access the current value of the outer loop and get the difference compared to the value of the inner loop. That this also works with negative numbers we just wrap it into an abs() call to make the difference always positive.

Then we just check if the difference is smaller than the smallest difference which we already found, saved in $nearest. (We initialized $nearest by the difference of the biggest and smallest value of the array + 1):

if( ($diff = abs($arr[$keys[$key]] - $arr[$keys[$innerKey]])) < $nearest)          

If the difference is smaller than the smallest difference which we already found, we write the two values into an array and set the new smallest difference:

$result = [$arr[$keys[$key]], $arr[$keys[$innerKey]]];
$nearest = $diff;

Code

<?php

    $arr = [20, 1, 5, 10, 7, 16];

    $keys = array_keys($arr);
    $nearest = max($arr) - min($arr) + 1;
    $result = [];

    for($key = 0, $length = count($arr); $key < $length; $key++){

        for($innerKey = $key + 1; $innerKey < $length; $innerKey++){

            if( ($diff = abs($arr[$keys[$key]] - $arr[$keys[$innerKey]])) < $nearest){
                $result = [$arr[$keys[$key]], $arr[$keys[$innerKey]]];
                $nearest = $diff;

            }

        }

    }

    print_r($result);

?>

Output

[5, 7]