Finding first available ID from an array

Given an array like this:

Array => (
  [0] => 1,
  [1] => 2,
  [2] => 3,
  [3] => 5,
  [4] => 6
)

What is the easiest way to find the first 'available' ID in that array – that is, the first value in the sequence [1,2,3...n] that does not exist in the array? In this case, the correct answer would be 4.

I can do this using some while loops or sorts with temp variables开发者_JAVA百科 but that's a bit messy, so I'm interested to see if anyone can come up with a 'clever' solution.

My PHP skills are a bit rusty, but couldn't you use range and array_diff:

$missing = array_diff(range(1, end($myArray)+ 1), $myArray);
echo $missing[0];

Updated with Tatu Ulmanen's corrections (i told ya my PHP was rusty ;-))

I can't really think up anything except sorting the array and going through it, looking for holes.

Maybe something like:

sort($array);
$next_available = array_shift($array);
foreach($array as $_k) {
    ++$next_available;
    if($_k > $next_available) {
        break;
    }
}
echo "Next available index: {$next_available}";

I don't believe this is less messy than some loop, but here goes my contrived example:

sort( $array );
$range = range( reset( $array ), end( $array ) );
$diff = array_diff( $range, $array );
$result = null != ( $result = array_shift( $diff ) ) ? $result : end( $array ) + 1;

This is a bit of magic, but does the trick:

$values = array_values($id_array);
$values[] = max($values) + 1;
$combined = array_values(array_flip($values) + array_keys($values));
$missing = isset($combined[count($values) + 1])
    ? $combined[count($values) + 1]
    : end($values);

The advantage of this is that it's considerably fast. The problem with using range() would be that single large key in a small array would make array_diff() very slow. In addition, this will return the next key if there are no gaps in the IDs (or you could change final end($values) to false, if that's what you would prefer).

Despite the cleverness, it's still slower than simply iterating through the array. But array_diff() (even without range()) would be much, much slower.

if your array use only numeric key and without hole, you can do $next_id = count($your_array)

if there is holes, ou can try

$keys = array_keys($your_array);
rsort($keys);
$next_id = empty($keys)?0:($keys[0]+1);