Summary:
In this laboratory, we explore different issues related to searching.
Contents:
Related Pages:
a. Start DrScheme.
b. Make sure that you understand the purpose of get-key in
binary-search from the
reading on searching.
c. Create a new file for this lab that contains the binary-search
procedure from that reading.
d. Here's a vector of lists of cartoon characters and sidekicks,
sorted by primary character. Put this vector in your file from step c.
;;; Name:
;;; cartoons
;;; Type:
;;; Ordered vector of two-element lists
;;; Value:
;;; Each two-element list contains a protagonist and a sidekick
;;; (in that order).
;;; The vector is ordered by protagonist.
(define cartoons
(vector
(list "Ash" "Misty")
(list "Asterix" "Obelix")
(list "Bart Simpson" "Milhouse Van Houten")
(list "Batman" "Robin")
(list "Bullwinkle" "Rocky")
(list "Dexter" "Didi")
(list "Dick Dastardly" "Muttley")
(list "Duck Dodgers" "Porky Pig")
(list "Fred" "Barney")
(list "Josie" "The Pussycats")
(list "Peabody" "Sherman")
(list "Peter Griffin" "Brian")
(list "Quick Draw McGraw" "Baba Looey")
(list "Ren" "Stimpy")
(list "Rocko" "Heffer")
(list "Scooby Doo" "Scrappy Doo")
(list "Scooby Doo" "Shaggy")
(list "Secret Squirrel" "Morocco Mole")
(list "Spongebob" "Patrick")
(list "Tennessee Tuxedo" "Chumley")
(list "Yogi" "Booboo")
(list "Yu-Gi-Oh" "Joey")
))
a. Verify that binary search can correctly find the entry for "Batman".
b. Verify that binary search can correctly find the entry for a character of your choice.
c. Verify that binary search can correctly find the first entry.
d. Verify that binary search can correctly find the last entry.
e. Verify that binary search terminates and returns -1 for something that would fall in the middle of the vector and is not there.
f. Verify that binary search terminates and returns -1 for something that comes before the first entry.
g. Verify that binary search terminates and returns -1 for something that comes after the last entry.
h. What does binary search do if there are duplicate keys?
a. Add calls to display and newline to the
definition of binary-search, so that it prints out the values
of lower-bound and upper-bound each time the
kernel procedure is called.
b. Redo steps a-g and report on the number of steps each search took.
The divide-and-conquer principle can be applied in other
situations. For example, we can apply it to a guessing game
in which one player, A, selects a number in the range from 1
to some value and the other player, B, tries to guess it by asking yes-or-no
questions of the form Is your number less than n?
(putting
in specific values for n). The most efficient strategy for B to
use is repeated bisection of the range within which A's number is known
to lie.
Write a Scheme procedure that takes the part of B in this game. Your
procedure should take the maximum possible value as a parameter. When
invoked, it should print out a question of the specified form and read in
the user's response (presumably, the symbol yes or the symbol
no), then repeat the process until the range of possible
values has been narrowed to contain only one number. The procedure should
then display and identify that number. A sample run might look like this:
> (guessing-game 100)
Is your number less than 51? yes
Is your number less than 26? no
Is your number less than 38? no
Is your number less than 44? no
Is your number less than 47? yes
Is your number less than 45? no
Is your number less than 46? no
Since your number is less than 47 but not less than 46, it must be 46.
It is sometimes useful to learn not just that something is not in the
vector, but where it would fall if it were in the vector.
Revise binary-search (both the code and the documentation) so that it
returns a "half value" if the value being searched for belongs between
two neighboring values. For example, if the key being searched for
is larger than the key at position 5 and smaller than the key at position
6, you should return 11/2. Similarly, if the key being searched for
is smaller than the key at position 0, you should return -0.5. If the
key being searched for is bigger than the largest key, return
(- (vector-length vec) 1/2).
;
Check with Bobby