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).