CSC151.02 2003F, Class 44: Binary Search and Such
Admin:
* No reading for Thursday
* Think about sorting mechanisms
* Questions on the homework?
Overview:
* Background on binary search
* What purpose do the parameters to binary-search serve?
* Explain the parameters to the kernel.
* Lab
* Reflection
(define binary-search
(lambda (key vec get-key less-than?)
; Search a portion of the vector from lower-bound to upper-bound
(let search-portion ((lower-bound 0)
(upper-bound (- (vector-length vec) 1)))
(if (<= lower-bound upper-bound)
(let* ((midpoint (quotient (+ lower-bound upper-bound) 2))
(middle-element (vector-ref vec midpoint))
(middle-key (get-key middle-element)))
(cond ((less-than? key middle-key)
(search-portion lower-bound (- midpoint 1)))
((less-than? middle-key key)
(search-portion (+ midpoint 1) upper-bound))
(else midpoint)))
-1))))
key, vec, get-key, less-than?
What is key? The value we're looking for.
What is vec? A vector of "keyed lists"
(key value value value)
("Rebelsky" "Sam" "4410")
("Stone" "John David" "1234")
What is get-key? Something that given a data item returns the key of that data item
* If we're sorted by last name and our entries look like the above, it's car
* If we're sorted by phone number and our entries look like the above, it's caddr
* If we're sorted by last name and first name and we want to look for the combination of the two, it's probably soemthing like
(lambda (entry) (string-append (car entry) ", " (cadr entry)))
* If we have a vector of numbers (that is, each entry is a number) and we want to simply see if a number is there, get-key will be ... (lambda (x) x)
Lab
* You can compare two strings with
string-ci