Exercise 2.61. Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.
如果检测到碰到的元素大于 x，那么之后就不必判断了，将 x 插入到那个元素之前。最坏的情况当然是将 x 插入到表的末尾，需要 n 步。但平均而言，x 将只需要 n/2 步就可以找到自己的位置。增长的速度是 O(n)。
(define (adjoin-set x set)
(cond ((null? set) '())
((> x (car set))
(cons (car set)
(adjoin-set x (cdr set))))
((= x (car set)) set)
((< x (car set))
(cons x set))))