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