Finding the first integer not used in a collection of integers

After retrieving a开发者_StackOverflow社区 list of integers used for ID in a mysql database, taking in that all the ID doesn't follow each other in each case (for example list could be [1,2,3,5,10,11,12,20,...]), what would be an more efficient way, aside from looping through all the integers, to find the lowest integer which isn't yet in the list (in our case, it would be 4, then 6 once 4 is attributed). Also it shouldn't be higher than 999.

This question give a mysql query, but I would like to do it in my php script, except if it would be more efficient.

This problem can be solved easily and efficiently using a binary search (which runs in O(log n), faster than a linear search, which is O(n)). The basic idea is that if and only if all the numbers are present up to a certain index, then list[index] = index + 1 (e.g. list[0] = 1, list[1] = 2, etc). This property can be used to determine whether the smallest missing number is before or after a certain element of the list, allowing for a binary search.

The implementation is simple (I don't know php, so here's pseudocode)

lower_bound = 0
upper_bound = length(list) - 1
index = floor((lower_bound + upper_bound) / 2)
while (lower_bound != upper_bound)  
     if(list[index] = index + 1)     // missing number is after index
          lower_bound = index + 1
          index = floor((lower_bound + upper_bound) / 2)
     else                            // missing number is at or before index
          upper_bound = index
          index = floor((lower_bound + upper_bound) / 2)
missing_number = upper_bound + 1     // add 1 because upper_bound is the index

And missing_number will be the smallest missing number, or if there are no missing numbers it will be length(list) + 1.

Or using recursion, which I hear is less efficient

first_missing_number(list, lower_bound, upper_bound) {
     if(lower_bound = upper_bound)  // found the first missing number
          return upper_bound + 1    // add 1 because upper_bound is the index
     index = floor((lower_bound + upper_bound) / 2)
     if (list[index] = index + 1)   // missing number is after index
          first_missing_number(list, index + 1, upper_bound)
     else                           // missing number is at or before index
          first_missing_number(list, lower_bound, index)
}

In which case first_missing_number(list, 0, length(list) - 1) will return the first number missing from the list. If there are no numbers missing, it returns length(list) + 1.

I hope this helps!

upd: php version

function first_free($list) {
    $lwr = 0;
    $upr = count($list);

    while ($lwr < $upr) { 
        $m = ($lwr + $upr) >> 1;
        if($list[$m] == $m + 1)
            $lwr = $m + 1;
        else
            $upr = $m;
    }
    return $upr + 1;
}

the most efficient way is the simple loop:

foreach($list as $n => $v)
   if($v !== $n + 1) return $n + 1;

You can use the array_diff() function:

eg:

<?php
$array1 = array("a" => "1", "2", "3", "4");
$array2 = array("b" => "2", "4");
$result = array_diff($array1, $array2);

print_r($result);
?>

this will give you the missing items in the second array:

Array
(
    [1] => 1
    [2] => 3
)

Maybe this will be more efficient way:

$your_list = array(....);
$number_you_want = min(array_diff(range(1,999), $your_list));

Since you are limited to only 999 possible keys, I'd probably create a temporary table with all possible keys (i.e. 1-999), or even create a permanent table just for this purpose, then you can do sql like this:

SELECT key_value FROM temp_key_table WHERE key_value NOT IN (SELECT key FROM original_table ORDER BY key ASC) ORDER BY key_value ASC LIMIT 1

Not sure how practical this is, and a SQL guru could probably give you a better solution, but this should work in a pinch, rather than messing with this in PHP.

$array   = array(1,2,3,5,10,11,12,20);
$missing = array_diff(range(min($array), max($array)), $array);

// First missing number is at $missing[0], next at $missing[1], etc.