CSC151, Class 43: Searching Overview: * What computer scientists do * A problem: Find something in a collection of values * A related problem: Find something in an ordered collection of values. * How we might do write it in Scheme? Notes: * Support the destruction of small-town America * Cool talk today at 4:15. Extra credit for attending. + Fleeting Fictions extra credit. + Participating in Andy's amusing experiment (dates next week) * Notes on extra credit available. * I'll be absent next Monday. In the long tradition of absent instructors, I will show a film. Please attend. * Planning ahead: Where should we hold the last day of class? + Side note on Saints' Rest vs. Coffee Company * Questions on project? ---------------------------------------- What computer scientists do ... Computer science is ... the study of algorithms * Look at general problems * Generalize * Design algorithms for generalized problems How do you look for "A" in a collection of things? Look at each thing in turn, comparing to the desired value until either (1) You run out of things (2) You find the thing you're looking for (define search (lambda (val lst) (cond ((null? lst) #f) ((equal? (car lst) val) (car lst)) (else (search val (cdr lst)))))) (define search (lambda (pred? lst) (cond ((null? lst) #f) ((pred? (car lst)) (car lst)) (else (search pred? (cdr lst)))))) (search prime? list-of-numbers) (define is-the-title-scheme? (lambda (book) (equal? (car book) "Scheme"))) (search is-the-title-scheme? books) (search (lambda (book) (equal? (car book) "Scheme")) books) You will search differently if you know something about the order of the element. You have an ordered collection of numbers (from smallest ot largest). Is 43 in that collection? (member 43 collection) Look in "the middle" Is the thing we're looking for larger or smaller than the middle element or equal? (cond ((equal? middle-element thing-were-looking-for) middle-element) ((less-than middle-element thing-were-looking-for) cut out the middle element and things smaller recurse on the remaining stuff ) (else cut out the middle element and things larger recurse on the remaining stuff)) Is this a better solution than member or search? Yes, it seems significantly more efficient Suppose there are 8000 names in the phone book. How many steps will it take to find someone? 8000/2^n = 1