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