Finding the first integer not used in a collection of integers

Question

After retrieving a 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.

Answer 1

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;
}

Answer 2

the most efficient way is the simple loop:

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