How do you find a missing number in a table field starting from a parameter and incrementing sequentially?

Question

Let's say I have an sql server table:

NumberTaken CompanyName

2                      Fred
3                      Fred
4                      Fred
6                      Fred
7                      Fred
8                      Fred
11                    Fred

I need an efficient way to pass in a parameter [StartingNumber] and to count from [StartingNumber] sequentially until I find a number that is missing.

For example notice that 1, 5, 9 and 10 are missing from the table.

If I supplied the parameter [StartingNumber] = 1, it would check to see if 1 exists, if it does it would check to see if 2 exists and so on and so forth so 1 would be returned here.

If [StartNumber] = 6 the function would return 9.

In c# pseudo code it would basically be:

int ctr = [StartingNumber]
while([SELECT NumberTaken FROM tblNumbers Where NumberTaken = ctr] != null)    
    ctr++;

return ctr;

The problem with that code is that is seems really inefficient if there are thousands of numbers in the table. Also, I can write it in c# code or in a stored procedure whichever is more efficient.

Thanks for the help

Answer 1

Try the set based approach - should be faster

select min(t1.NumberTaken)+1 as "min_missing" from t t1
where not exists (select 1 from t t2 
                   where t1.NumberTaken = t2.NumberTaken+1)
and t1.NumberTaken > @StartingNumber

This is Sybase syntax, so massage for SQL server consumption if needed.

Answer 2

A solution using JOIN:

select min(r1.NumberTaken) + 1
from MyTable r1
left outer join MyTable r2 on r2.NumberTaken = r1.NumberTaken + 1
where r1.NumberTaken >= 1 --your starting number
    and r2.NumberTaken is null

Answer 3

I called my table Blank, and used the following:

declare @StartOffset int = 2
; With Missing as (
    select @StartOffset as N where not exists(select * from Blank where ID = @StartOffset)
), Sequence as (
    select @StartOffset as N from Blank where ID = @StartOffset
    union all
    select b.ID from Blank b inner join Sequence s on b.ID = s.N + 1
)
select COALESCE((select N from Missing),(select MAX(N)+1 from Sequence))

You basically have two cases - either your starting value is missing (so the Missing CTE will contain one row), or it's present, so you count forwards using a recursive CTE (Sequence), and take the max from that and add 1

Edit from comment. Yes, create another CTE at the top that has your filter criteria, then use that in the rest of the query:

declare @StartOffset int = 2
; With BlankFilters as (
    select ID from Blank where hasEntered <> 1
), Missing as (
    select @StartOffset as N where not exists(select * from BlankFilters where ID = @StartOffset)
), Sequence as (
    select @StartOffset as N from BlankFilters where ID = @StartOffset
    union all
    select b.ID from BlankFilters b inner join Sequence s on b.ID = s.N + 1
)
select COALESCE((select N from Missing),(select MAX(N)+1 from Sequence))

this may now return a row that does exist in the table, but hasEntered=1

Tables:

create table Blank (
    ID int not null,
    Name varchar(20) not null
)
insert into Blank(ID,Name)
select 2 ,'Fred' union all
select 3 ,'Fred' union all
select 4 ,'Fred' union all
select 6  ,'Fred' union all
select 7 ,'Fred' union all
select 8 ,'Fred' union all
select 11 ,'Fred'
go

Answer 4

Create a temp table with all numbers from StartingValue to EndValue and LEFT OUTER JOIN to your data table.