Finding gaps in sequence of numbers

Question

I have a std::vector containing a handful of numbers, which are not in any particular order, and may or may not have gaps between the numbers - for example, I may have { 1,2,3, 6 } or { 2,8,4,6 } or { 1, 9, 5, 2 }, etc.

I'd like a simple way to look at this vector and say 'give me the lowest number >= 1 which does not appear in the vector'. So,

for the three examples above, the answers would be 4, 1 and 3 respectively.

It's not performance critical, and the list is short so there aren't any issues about copying the list and sorting it, for example.

I am not really stuck for a way to do this, but my STL skills are seriously atrophied and I can feel that I'm about to do something inelegant - I would be interested to see what other people came up with.

Answer 1

The standard algorithm you are looking for is std::adjacent_find.

Here is a solution that also uses a lambda to make the predicate clean:

int first_gap( std::vector<int> vec )
{
  // Handle the special case of an empty vector.  Return 1.
  if( vec.empty() )
    return 1;

  // Sort the vector
  std::sort( vec.begin(), vec.end() );

  // Find the first adjacent pair that differ by more than 1.
  auto i = std::adjacent_find( vec.begin(), vec.end(), [](int l, int r){return l+1<r;} );

  // Handle the special case of no gaps.  Return the last value + 1.
  if ( i == vec.end() )
    --i;

  return 1 + *i;
}

Answer 2

The checked answer uses < for comparison. != is much simpler:

int find_gap(std::vector<int> vec) {
    std::sort(vec.begin(), vec.end());
    int next = 1;
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        if (*it != next) return next;
       ++next;
    }
    return next;
}

find_gap(1,2,4,5) = 3
find_gap(2) = 1
find_gap(1,2,3) = 4

I'm not passing a reference to the vector since a) he said time doesn't matter and b) so I don't change the order of the original vector.

Answer 3

Sorting the list and then doing a linear search seems the simplest solution. Depending on the expected composition of the lists you could use a less general purpose sorting algorithm, and if you implement the sort yourself you could keep track of data during the sort that could be used to speed up (or eliminate entirely) the search step. I do not think there is any particularly elegant solution to this problem