/*******************************************************************************
  Create staging table for missing gap test
*******************************************************************************/
SET NOCOUNT ON

CREATE TABLE	#Sample
	(
		ID INT PRIMARY KEY CLUSTERED
	)

-- Define which ID is missing
DECLARE	@ID INT

-- Use     1 for low  missing value test
-- Use 16379 for high missing value test
SET	@ID = ABS(CHECKSUM(NEWID())) % 16384

SELECT	@ID AS theMissingID

-- Populate staging table
INSERT		#Sample
SELECT		v.Number + 2048 * x.i
FROM		master..spt_values AS v
CROSS JOIN	(
			SELECT 0 AS i UNION ALL
			SELECT 1 UNION ALL
			SELECT 2 UNION ALL
			SELECT 3 UNION ALL
			SELECT 4 UNION ALL
			SELECT 5 UNION ALL
			SELECT 6 UNION ALL
			SELECT 7
		) AS x
WHERE		v.Type = 'P'

DELETE
FROM	#Sample
WHERE	ID IN (@ID, @ID + 1, @ID + 2, @ID + 4, @ID + 5, @ID + 6)
	OR ID IN (@ID + 9, @ID + 10, @ID + 11)

/*******************************************************************************
  Setup participants queries
*******************************************************************************/

-- Peso 1 with {low 6, high 58} reads
SELECT TOP 1	s.ID + 1 AS [Peso 1 ID]
FROM		#Sample AS s
WHERE		NOT EXISTS (SELECT * FROM #Sample AS t WHERE t.ID = s.ID + 1)

-- Peso 2 with {low 29, high 29} reads
SELECT	MAX(ID) + 1 AS [Peso 2 ID]
FROM	(
		SELECT		TOP 1 WITH TIES
				ID
		FROM		#Sample
		ORDER BY	ID - ROW_NUMBER() OVER (ORDER BY ID)
	) AS d

-- Charlie 1 with {low 58, high 58) reads
SELECT		MIN(s.ID) + 1 AS [Charlie 1 ID]
FROM		#Sample AS s
LEFT JOIN	#Sample AS s2 ON s2.ID = s.ID + 1
WHERE		s2.ID IS NULL

-- Charlie 2 with {low 29, high 29) reads
SELECT	MAX(rowNumber) + 1 AS [Charlie 2 ID]
FROM	(
		SELECT	ROW_NUMBER() OVER (ORDER BY ID) - 1 AS rowNumber,
			ID
		FROM	#Sample
	) AS s
WHERE	s.ID = s.rowNumber

-- Hanbingl 1 with {low 6, high 58} reads
SELECT	TOP 1
	ID AS [Hanbingl 1 ID]
FROM	(
		SELECT ID + 1 AS ID
		FROM	#Sample 

		EXCEPT

		SELECT	ID
		FROM	#Sample
	) AS t

-- Hanbingl 2 with {low 27, high 163807} reads
;WITH findMe(ID)
AS ( 
	SELECT	MIN(ID)
	FROM	#Sample

	UNION ALL

	SELECT		fm.ID + 1
	FROM		findMe AS fm
	INNER JOIN	#Sample AS s ON s.ID = fm.ID
)

SELECT	MAX(ID) AS [Hanbingl 2 ID]
FROM	findMe 
OPTION	(MAXRECURSION 0)

-- Fribble 1 with {low 4, high 31} reads
SELECT TOP 1	r AS [Fribble 1 ID]
FROM		(
			SELECT	ID,
				ROW_NUMBER() OVER (ORDER BY ID) + (SELECT MIN(ID) FROM #Sample) - 1 AS r
			FROM	#Sample
		) AS a
WHERE		ID <> r
ORDER BY	ID

/*******************************************************************************
  Clean up
*******************************************************************************/

DROP TABLE	#Sample

SELECT MIN(s.[Id]) + 1
FROM
	#sample s
	LEFT JOIN #sample s2 ON s2.[Id] = s.[Id] + 1
WHERE
	s2.[Id] IS NULL

SELECT
	MAX([rownumber]) + 1
FROM
	(
	SELECT
		ROW_NUMBER() OVER(ORDER BY [Id] ASC) - 1 AS [rownumber]
		, [Id] AS [Id]
	FROM
		#sample
	)
	s
WHERE
	s.[ID] = s.[rownumber]

SELECT
	 MIN([rownumber]) AS [Charlie - ROWNUMBER]
FROM
	(
	SELECT
		ROW_NUMBER() OVER(ORDER BY [Id] ASC) - 1 AS [rownumber]
		, [Id] AS [Id]
	FROM
		#sample
	)
	s
WHERE
	s.[ID] <> s.[rownumber]

-- Charlie -- Test ROWNUMBER

DECLARE @start INT
SELECT @start = MIN([Id]) FROM #sample

SELECT
	 MIN([rownumber]) AS [Charlie - ROWNUMBER]
FROM
	(
	SELECT
		ROW_NUMBER() OVER(ORDER BY [Id] ASC) - 1 + @start AS [rownumber]
		, [Id] AS [Id]
	FROM
		#sample
	)
	s
WHERE
	s.[ID] <> s.[rownumber]

quote:

---

-- Peso 2 with {low 6, high 6} reads
SELECT	MAX(ID) + 1 AS [Peso 2 ID]
FROM	(
		SELECT		TOP 1 WITH TIES
				ID
		FROM		#Sample
		ORDER BY	ID - ROW_NUMBER() OVER (ORDER BY ID)
	) AS d

---

SELECT TOP 1 r
FROM (
    SELECT ID, ROW_NUMBER() OVER (ORDER BY ID) +
      ( SELECT MIN(ID) FROM #Sample ) - 1 AS r
    FROM #Sample
  ) AS A
WHERE ID <> r
ORDER BY ID

quote:

---

Originally posted by Peso
And sometimes the ID will be found in the table as "missing".

---

-- Charlie 3 (Set based)
SELECT
	[Rownumber]
FROM
	(
	SELECT
		ROW_NUMBER() OVER (ORDER BY [Id] ASC) + 1 AS [Rownumber]
	FROM
		#sample
	)
	s
WHERE
	[rowNumber] NOT IN (SELECT [Id] FROM #sample)