CSC151, Class 44: Binary Search
Topics:
* Binary search implemented
* Questions and answers on searching
Notes:
* We may have admittees visiting
* Please email me the current status of your project
Don't forget amount of time
* Cool independent in the fall
Why come to Grinnell? (For admittees and relatives)
* Self-governance: Students try to set rules for themselves.
* Highest-paid college president. Yay!
* Get to know your professors well. They ocassionally
sympathize.
* Students know each other and talk casually in many
fora, including classes.
Do we have to document everything with the six P's?
* Only primary procedures.
* But I want a sentence abuot every procedure.
* No, you don't have to document data.
----------------------------------------
You can search efficiently if the collection you are searching
is ordered (e.g., from smallest to largest)
(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))
If we're using lists, this will not be an efficient mechanism
to searching.
* We'll need to cdr through the list "eight zillion times"
to get to the middle.
* We need to use vectors.
+ Vectors are fixed size we can specify
+ Easy/quick to get the nth element for any n.
* Lists also take up more memory [Brett]
* However, lists are dynamic (we can add new element),
vectors are not.
Both Andy and Kirsten worry about cutting the vector in half.
* Solution: Use two integers, lb and ub, that describe the
portion of interest. lb is the *index* of the smallest
value in the portion still of interest. ub is the *index*
of the largest such value.
The value we're looking for must
be between index lb and index ub, inclusive.
(define binary-search-kernel
(lambda (value vec lb ub lessthan?)
(let ((mid (quotient (+ lb ub) 2)))
(cond
; Base case: What if lb = ub?
; See if value is equal to the value at that
; position. If so, return the value at the
; position.
; Base case: If the middle is equal to the
; desired element, return the middle.
((equal? (vector-ref vec mid) value)
(vector-ref vec mid))
; Recursive case: Middle element is too large.
((lessthan? value (vector-ref vec mid))
(binary-search kernel value vec lb (- mid 1)))
; Recursive case: Middle element is too small.
(else
(binary-search kernel value vec (+ mid 1) ub))
...)
Question: How do we find the index of the middle element?
(1) Find the length of the portion of interest
E.g., if lb is 5 and ub is 11, length is 7
IN general 1+ub-lb
(2) Problem: What if there are an even number of elements,
so there is no middle?
Answer: Either one of the things near the middle suffices.
Take length of portion of interest, divide by 2, round down
Add to lb
Suppose you have seven elements, numbered 0 through 6
length is 7
* If you choose 3 as the middle element, there are three
smaller elements and 3 larger elements
* If you choose 4 as the middle element, there are two
larger elements and four smaller elements (not a very
even split).
Suppose you have seven elements, numbered 11 thorough 17
...
lb + (ub - lb + 1) / 2 round down
Renegade suggestion
(lb+ub) / 2 , round up
(quotient (+ lb ub) 2)