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