The term ``binary search'' is applied both to searching by index in a sorted vector and to searching within some linked structure such as a binary search tree. We'll consider both variations.
The Scheme code for binary search in a sorted vector is straightforward:
The variables start and stop keep track of the
leftmost and rightmost position that could still be occupied by the datum
sought, and the subvector they bound is bisected and narrowed until the
datum is found or the subvector is null. Replacing the final
#t with midpoint yields a version that reports
the position of the item if the search is successful.
(define binary-search
(lambda (vec sought . opt)
(let ((precedes? (if (null? opt) < (car opt))))
(let loop ((start 0)
(stop (- (vector-length vec) 1)))
(if (< stop start)
#f
(let* ((midpoint (quotient (+ start stop) 2))
(mid-value (vector-ref vec midpoint)))
(cond ((precedes? sought mid-value)
(loop start (- midpoint 1)))
((precedes? mid-value sought)
(loop (+ midpoint 1) stop))
(else #t))))))))
For search in a binary search tree, let's begin by creating an abstract
data type for such trees. A binary search tree is either empty or a
structure comprising a datum and two binary search trees. It seems most
natural to use the null object for an empty binary search tree and a
three-element vector for a non-empty one. Having chosen this
representation, we can easily provide an assortment of constructors,
selectors, and mutators:
(define empty-bst '())
(define empty-bst? null?)
(define cons-bst
(lambda (datum left-subtree right-subtree)
(vector datum left-subtree right-subtree)))
(define bst-datum
(lambda (bst)
(vector-ref bst 0)))
(define bst-left-subtree
(lambda (bst)
(vector-ref bst 1)))
(define bst-right-subtree
(lambda (bst)
(vector-ref bst 2)))
(define set-bst-datum!
(lambda (bst new-datum)
(vector-set! bst 0 new-datum)))
(define set-bst-left-subtree!
(lambda (bst new-left-subtree)
(vector-set! bst 1 new-left-subtree)))
(define set-bst-right-subtree!
(lambda (bst new-right-subtree)
(vector-set! bst 2 new-right-subtree)))
Cons-bst is perhaps too low-level a constructor for regular
use. Here's insert!, which takes a binary search tree and a
new datum, and returns the binary search tree with the new datum placed
correctly in it (according to the ordering specified by the optional
parameter, or < if none is provided).
(define insert!
(lambda (bst new-datum . opt)
(let ((leaf (cons-bst new-datum empty-bst empty-bst)))
(if (empty-bst? bst)
leaf
(let ((precedes? (if (null? opt) < (car opt))))
(let loop ((root bst))
(if (precedes? new-datum (bst-datum root))
(let ((left-child (bst-left-subtree root)))
(if (empty-bst? left-child)
(set-bst-left-subtree! root leaf)
(loop left-child)))
(let ((right-child (bst-right-subtree root)))
(if (empty-bst? right-child)
(set-bst-right-subtree! root leaf)
(loop right-child)))))
bst)))))
Using this procedure, then, we can easily build a binary search tree
containing the elements of a given list:
(define list->bst
(lambda (ls . opt)
(let ((precedes? (if (null? opt) < (car opt))))
(let loop ((rest ls)
(result empty-bst))
(if (null? rest)
result
(loop (cdr rest) (insert! result (car rest) precedes?)))))))
Once the binary search tree has been constructed, the binary search method
is straightforward:
(define binary-search
(lambda (bst sought . opt)
(let ((precedes? (if (null? opt) < (car opt))))
(let loop ((subtree bst))
(if (empty-bst? subtree)
#f
(let ((root-datum (bst-datum subtree)))
(cond ((precedes? sought root-datum)
(loop (bst-left-subtree subtree)))
((precedes? root-datum sought)
(loop (bst-right-subtree subtree)))
(else
#t))))))))
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/events/scheme-workshop/binary-search.html