Binary Search

a. Verify that binary search can correctly find the entry for "Heather" in objects-by-name. That is, write an expression to find "Heather".

> (binary-search objects-by-name ___ ___ "Heather")

b. Verify that binary search can correctly find the entry for an object of your choice in objects-by-name.

c. Verify that binary search can correctly find the first entry in objects-by-name. You will need to supply the name associated with that entry.

d. Verify that binary search can correctly find the last entry in objects-by-name. You will need to supply the name associated with that 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. That is, pick a name that starts with M or N and that does not appear in the vector.

f. Verify that binary search terminates and returns -1 for something that comes before the first entry in objects-by-name. You will need to pick a name that alphabetically precedes "Amy".

g. Verify that binary search terminates and returns -1 for something that comes after the last entry. You will need to pick a name that alphabetically follows "Zed".

It is often useful when exploring a recursive algorithm to observe the steps the algorithm performs. In Scheme, we can sometimes observe steps in recursive calls by inserting code to display the parameters of the procedure at each recursive call.

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 of Exercise 1 and report on the number of steps each search took.

c. Optional: You might also use define$ and analyze to do the counting for you.

a. What do you expect binary search do if there are entries with duplicate keys?

b. Add two more entries with a key of "Otto" and two more entries with a key of "Amy". These new entries should be slightly different, so that you can tell them apart.

c. Which of the three do you expect binary search to return if you search for "Otto"?

d. Check your answer experimentally.

e. Which of the three do you expect binary search to return if you search for "Amy"?

f. Check your answer experimentally.

g. What does your experience in this exercise suggest about what binary search will do with multiple keys?

As you may have observed, objects-by-width contains the same twenty-six objects as in object-by-name, but with the objects organized by their width, rather than by name.

a. Write an expression to find an object with a width of 45.

> (binary-search objects-by-width ___ ___ 45)

b. Write an expression to find an object whose width is 40.

c. Write an expression to find an object whose width is 35.

d. What, if anything, can you say about what binary search does when searching for a key that appears more than once in the vector?

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. Write documentation and code for new-binary-search that mostly behaves like binary-search, except 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 5.5. Similarly, if the key being searched for is smaller than the key at position 0, you should return -1/2. If the key being searched for is bigger than the largest key, return (- (vector-length vec) 0.5).

For example,

> (new-binary-search objects-by-name car string=<? "Andy")
0.5
> (new-binary-search objects-by-name car string=<? "Greg")
7
> (new-binary-search objects-by-name car string=<? "Heather")
8
> (new-binary-search objects-by-name car string=<? "Hanna")
7.5
> (new-binary-search objects-by-width (r-s list-ref 5) <= 1)
0.5
> (new-binary-search objects-by-width (r-s list-ref 5) <= 6)
3.5
> (new-binary-search objects-by-width (r-s list-ref 5) <= 60)
25.5

You should use the code for binary-search as your starting point.

Here are commands to search objects-by-name for "Paula" and objects-by-width for something with width 45.

> (binary-search objects-by-name car string<=? "Paula")
> (binary-search objects-by-width (r-s list-ref 5) <= 45)

a. What do you expect to have happen if we swap the vectors in these commands, as in the following?

> (binary-search objects-by-width car string<=? "Paula")
> (binary-search objects-by-name (r-s list-ref 5) <= 45)

b. Check your answer experimentally.

c. Try searching objects-by-width for the names "Otto", "Erin", "Fred", "Charlotte", "Janet", and "Xerxes".

d. What do the previous steps of this experiment tell you about binary search?

As you may recall from Exercise 4, when searching for objects by width, we got only one of a variety of objects with a particular width. In some cases, it's useful to find not just some object of a particular width, but how many objects have that width, or have a width of that size or less.

a. One technique for finding out how many objects have a certain width or less is to step through the vector until we find the first object wider than the desired width. Using this technique, write a procedure, (no-wider-than objects width), that, given a vector of objects sorted by width, finds the number of objects that are no wider than width.

b. A more efficient way to find the position is to use a variant of binary search. Once again, our goal is to find the first object wider than the desired width. However, this time we use binary search to find that object. That is, you look in the middle. If the middle object is wider than the desired width, recurse on the left half, but also include the middle element since that may be the one we're looking for. If the middle object is not wider than the desired width, recurse on the right half. Write a new version of no-wider-than that uses this technique.

Note: For part b, note that you cannot call the binary-search procedure directly. Rather, you will need to use it as a template for your code. That is, copy the procedure and then make modifications as appropriate.

As you've observed, when a key is repeated, binary search picks one value with that key, but not necessarily the first value with that key. We might want to write a variant, newer-binary-search, that uses the ideas of binary search to find the first element in the vector that contains the given key.

a. One strategy for implementing newer-binary-search is to find some value with the given key (which binary search already does) and then to step left in the vector until you find the first value with that key. Implement newer-binary-search using that strategy.

b. Of course, we use the binary search technique so that we don't have to step through elements one-by-one. Rewrite newer-binary-search so that it continues to “divide and conquer” in its attempt to find the first element with that key.