smallest-nonmember-problem


Given a finite set S of non-negative integers, the smallest-nonmember problem (Chapter 1) finds the smallest non-negative integer not in S. For example, { 0 1 3 } -> 2.

Here are three solutions, with successive solutions having asymptotically better worst-case behavior than the previous solutions.

 (define (smallest-nsq s) 
    
   ; Return the smallest non-negative integer not in s, a set 
   ; of non-negative integers. 
    
   (let ((n (length s))) 
     (let loop ((i 0)) 
       (if (and (< i n) (member i s)) 
         (loop (+ i 1)) 
         i)))) 
  
  
 (define (smallest-nlogn s) 
    
   ; Return the smallest non-negative integer not in s, a set 
   ; of non-negative integers. 
    
   (let ((s (sort s <))) 
     (let loop ((smallest 0) (s s)) 
       (if (null? s) 
         smallest 
         (let ((i (car s))) 
           (if (= smallest i) 
             (loop (+ smallest 1) (cdr s)) 
             smallest)))))) 
  
  
 (define (smallest-linear s) 
    
   ; Return the smallest non-negative integer not in s, a set 
   ; of non-negative integers. 
    
   (let* ((n (length s)) 
           (found (make-vector (+ n 1) #f))) 
      
      (let loop ((s s)) 
        (unless (null? s) 
          (let ((i (car s))) 
            (when (<= i n) 
              (vector-set! found i #t)) 
            (loop (cdr s))))) 
      
      (let loop ((i 0)) 
        (if (vector-ref found i) 
           (loop (+ i 1)) 
           i)))) 

Caveats: smallest-nsq may not have O(n^2) worst-case behavior if member doesn't have linear behavior (e.g., it's implemented using a hash table, which seems unlikely). smallest-nlogn may not have O(n log n) worst-case behavior if sort doesn't have O(n log n) worst-case behavior (e.g., is insertion sort, or quicksort with unintelligent pivot selection on ordered data).