Binary Search

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 b-h of Check 3 from the reading and report on the number of steps each search took.

a. What do you expect binary search to 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. Make sure you keep your vector in sorted order.

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.

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.

Note: If you find it more natural to represent the indices as exact numbers, rather than inexact numbers, you should feel free to do so.

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.