Problems for Session A2: Searching

Problem A3-A: An iterative binary search

Rewrite the binary search given in IntSeq.java iteratively; that is, use loops rather than recursive calls.

Problem A3-B: Evaluating binary search

Build an ordered array of the first sixteen positive even integers (2, 4, ..., 32). For each integer N between 1 and 33, find the number of steps required to determine whether or not N is in the array.

Problem A3-C: Searching through names

Build a StringSeq class that provides many of the same facilities as IntSeq, but which uses arrays of strings rather than arrays of integers. You need not include the various fill methods.

Problem A3-D: Finding the first element

As we saw in Experiment A3.5, binary search does not always find the first instance of an element in the array. Rewrite binary search so that it finds the first instance of each element. For example, in searching through [1,1,1,2,2,2,3,3,3], your algorithm should give 0 as the position of 1, 3 as the position of 2, and 6 as the position of 3.

Problem A3-E: Extending the number game

As you may recall, the NumberGameGuesser restricted the possible range to values between Long.MIN_VALUE/2 and Long.MAX_VALUE/2. Remove that restriction and see what happens when you try using values outside those ranges.

The problem you will encounter has to do with the computation (lower+upper)/2. While the result of that computation will always be between Long.MAX_VALUE and Long.MIN_VALUE, the intermediate value (lower+upper) may be too large or too small.

Rewrite (lower+upper)/2 so that it never gets too large or too small.

Problem A3-F: Variations on search

At the end of the discussion, we considered an alternate searching problem: searching for the smallest element in a list of elements. Are there other related searching problems you can think of?

Problem A3-G: Smallest, revisited

It seems somewhat odd that we have a different search method for finding the smallest element and for finding a particular element. Consider how you might write one method that could be used to solve both problems. For example, you might pass an Evaluator object (one that you design and construct) to the Search method, and that object will determine what to do at each step.

Problem A3-H: Further readings

In the books Programming Pearls (Addison-Wesley, 1986) and More Programming Pearls (Addison-Wesley, 1988), Jon Bentley reports on a number of aspects of binary search. Find the books, read the appropriate sections, and write a short report on them.