This class will not be recorded!
Approximate overview
Elided.
(or E1 E2 E2 ...) evaluates each expression in turn and returns
(a) the value of the first truish expression or (b) #f, if none
are truish.
(and E1 E2 E2 ...) evaluates each expression in turn and returns
(a) #f, if any are false, or (b) the value of the last expression,
if all are truish.
0 : "Aardvark"
1 : "Anteater"
2 : "Badger"
3 : "Bear"
4 : "Bonobo"
5 : "Cheetah"
6 : "Chinchilla"
7 : "Chupacabra"
8 : "Dingo"
9 : "Gnu"
10 : "Hedgehog"
11 : "Jackalope"
12 : "Koala"
13 : "Narwhal"
14 : "Ocelot"
15 : "Orangutan"
16 : "Squirrel Monkey"
17 : "Tapir"
18 : "Tiger"
19 : "Wildebeest"
20 : "Zebra"
a. Search for "Dodo".
lower-bound is 0, upper-bound is 21
; our traditional "lower-bound inclusive, upper-bound exclusive"
; midpoint (quotient (+ lower-bound upper-bound) 2)]
midpoint is 10, middle-key is "Hedgehog"
; "Dodo" comes before "Hedgehog", so (search-portion lower-bound midpoint)
lower-bound is 0, upper-bound is 10
midpoint is 5, middle-key is "Cheetah"
; "Dodo comes after "Cheetah"
; (search-portion (+ midpoint 1) upper-bound)
lower-bound is 6, upper-bound is still 10
midpoint is 8, "Dingo"
; "Dodo" comes after "Dingo"
lower-bound is 9, upper-bound is still 10
midpoint is 9, "Gnu"
; "Dodo" comes before "Gnu"
lower-bound remains 9, upper-bound is now 9
; (if (lowerbound >= upperbound) #f
#f
Key idea of binary search: If the things are in order, and we’ve decided our value is greater than the element we’ve just looked at, it can’t be anywhere to the left of the value we looked for. (Reverse for right). Each time, we can discard half the values we’re looking for.
b. Search for “Ocelot”
lower-bound is 0, upper-bound is 21
midpoint: 10, middle-key is "Hedgehog"
; "Ocelot" comes after "Hedgehog"
lower-bound is 11 (midpoint + 1), upper-bound is 21
midpoint: 16, middle-key "Squirrel Monkey"
; "Ocelot" comes before "Squirrel Monkey"
lower-bound is 11, upper-bound is 16 (upper-bounds are exclusive)
midpoint: 13, middle-key is "Narwhal"
; "Ocelot" comes after "Narwhal"
lower-bound is 14, upper-bound is 16
midpoint is 15, middle-key is "Orangutan"
; "Ocelot" comes before "Orangutan"
lower-bound is 14, upper-bound is 15
midpoint is 14, middle-key is "Ocelot"
; FOUND
Return 14
Elided
Elided
Elided
Elided
Elided