March 23, 2009
Our binary search sets the variables
hi to the two ends of the vector, and maintains the invariant that if the target number is present, it must be between
lo ever exceeds
hi, we report that the target number is not present. Otherwise, we calculate the mid-point of the vector and make a three-way decision: if the number at the mid-point is the target number, we report success, otherwise we loop on the appropriate sub-vector:
(define (bsearch t vs)
(let loop ((lo 0) (hi (- (vector-length vs) 1)))
(if (< hi lo) -1
(let ((mid (quotient (+ lo hi) 2)))
(cond ((< t (vector-ref vs mid))
(loop lo (- mid 1)))
((< (vector-ref vs mid) t)
(loop (+ mid 1) hi))
Our test generates two types of vectors and tests each for all sizes from zero to a user-requested limit. The first vector has the integers from 0 to limit-1, and tests each number from 0 to limit-1 for a successful search, plus the two fractions 1/2 above and below each number from 0 to limit-1 for unsuccessful search. The first vector has all elements set to 1, and searches for 1 for a successful search and 1/2 and 3/2 for an unsuccessful search.
Assert is a macro that compares its two arguments and reports if they are not equal; the message includes the text of the expression, making it easy to see what failed.
Range returns a list of non-negative integers less than n. Both appear in the Standard Prelude.
(define (test-search limit)
(do ((n 0 (+ n 1))) ((= n limit))
(let ((in-order (list->vector (range n)))
(all-equal (make-vector n 1)))
(do ((i 0 (+ i 1))) ((= i n))
(assert (bsearch i in-order) i)
(assert (bsearch (+ i 1/2) in-order) -1)
(assert (bsearch (- i 1/2) in-order) -1))
(assert (bsearch 1/2 all-equal) -1)
(assert (bsearch 3/2 all-equal) -1)
(if (positive? n) (assert (< -1 (bsearch1 all-equal) n) #t)))))
Performing the test shows that all is well:
> (test-search 12)
This solution is available at http://programmingpraxis.codepad.org/UxAnLcJF.
Pages: 1 2