In this laboratory session, you will investigate a number of algorithms for searching; that is, finding an element in a collection. Search is one of the most basic and most instructive introductory problems in computer science. The goals of this laboratory session are to:
Prerequisite skills:
Required files:
NumberGame.java
NumberGameOracle.java
NumberGameGuesser.java
IntSeq.java
IntSeqTester.java
SimpleInput.java
SimpleOutput.java
In previous experiments, we've worked with a variety of collections of elements. Why? Because a wide variety of problems in life (and therefore in computing) have to do with collections. For example, the phone book is a collection of name/number entries; most people have file cabinets that collect papers; many people collect other objects, such as books, records, beer cans, and autographs.
One of the most common problems relating to collections is that of searching. Given a collection, determine whether the collection contains a particular object. For example,
Since arrays provide one of the simplest and most universal mechanisms for collecting elements, we will primarily consider search algorithms as they pertain to arrays. In particular, we build search algorithms that determine the position of an integer in an array of integers. (You should be able to generalize these algorithms for other cases.)
Rather than working directly with arrays, we will build a new
class IntSeq for ``sequences'' of integers. How
do these sequences differ from arrays?
IntSeqs will be objects (arrays are also objects, but we'll
be able to use the syntax of objects with sequences).
IntSeqs will support a number of algorithms pertaining to
sequences and arrays, particularly searching algorithms.
IntSeqs will expand when needed.
IntSeqs will provide a number of mechanisms for
filling in a number of elements.
IntSeqs will support a toString method.
In Experiment A2.1, you will consider the
IntSeq class.
If we are going to search through arrays of numbers, generating
``random'' sequences of numbers will be useful. What do we mean by
``random''? Typically, random means that each sequence of a
particular size is equally likely or that at each point in the sequence,
each number is equally likely as the next element. How can we generate
such sequences? Fortunately, Java provides a standard utility class,
java.util.Random. This class includes a
nextInt method that gives that next ``random'' number in
the sequence. In truth, this number is not random, in that it is
generated by an algorithm. However, it is close enough to random for
our purposes.
Hence, to fill the array elements with a random sequence of 100
integers, we might write
import java.util.Random;
...
int i;
Random generator = new Random();
elements = new int[100];
for (i = 0; i < 100; ++i) {
elements[i] = generator.nextInt();
} // for
However, when we're comparing two algorithms, to have the same input to both algorithms is helpful. Fortunately, Java's random number generator can take a seed that uniquely determines the random sequence. You can think of a seed as being a number for the sequence. If you use the same seed, you end up with the same sequence. For example, to get the first sequence, you would write
Random generator = new Random(1);
Note that random sequences are not always the best test cases for your algorithms. For example, when testing an algorithm on sequences, you should also test sequences of varying lengths, sequences which contain all the same value, sorted sequences, and backwards sorted sequences (in which the numbers are organized largest to smallest). Nonetheless, random sequences still serve many purposes and are often a good starting point.
In Experiment A2.2 you will investigate random number generators.
Sequential search is a straightforward attempt to solve the problem. In sequential search, we look at the elements of the array, one by one, until we find the element or run off of the array. In the former case, we return the index of the matching item. In the latter case, we return an error value (negative one is a good choice).
Here is a simple sequential search method written in Java. It is one
of the methods supplied by IntSeq, which uses
this.elements as the array to search through.
/**
* Search through the sequence of integers for a particular value.
* Return the index of the value if it is found.
* Return -1 otherwise.
*/
public int sequentialSearch(int val) {
// An index into the sequence.
int i;
// Check each position of the array
for (i = 0; i < this.elements.length; ++i) {
// If the value is at position i, we're done.
return i;
} // if
} // for
// Unable to find the element. Return -1.
return -1;
} // sequentialSearch(int)
Sequential search is useful and correct. However, it may also be slow. In particular, sequential search looks at all of the elements in the array. For example, if the array has one million elements, it may be necessary to look at one million elements. Even if each look takes 1/1000 of a second, this will take 1000 seconds or sixteen minutes. Can we do better? As we'll soon see, the answer is yes, but only in certain cases.
In Experiment A2.3 you will investigate sequential search.
In the session on recursion, you encountered a simple game (guess a number) and a simple but fast strategy for guessing the number. This game illustrates one type of search: We are searching for a matching number in the set of numbers; we just don't know what number we're matching. The strategy is
guess the midpoint of the range of valid answers if it's correct, we're done if it's too small, shrink the range and try again if it's too large, shrink the range and try again
The following class implements the guessing strategy and reports on the steps it uses.
/**
* An ``intelligent'' number guesser that can guess numbers within a
* particular range, provided an oracle can tell it a little about its
* guesses.
*
* @author Samuel A. Rebelsky
* @version 1.0 of January 1999
*/
public class NumberGameGuesser {
// +---------+-----------------------------------------------------------
// | Methods |
// +---------+
/**
* Try to guess a number in the range [lower ... upper]. Only the
* oracle knows the correct answer. The upper end of the range cannot
* be larger than Long.MAX_VALUE/2, and the lower end of the range
* cannot be smaller than Long.MAX_VALUE/2 (see if you can figure out
* why).
*/
void guessNumber(long lower, long upper,
SimpleOutput out,
NumberGameOracle oracle) {
// Make sure there are possibilities.
if (upper < lower) {
out.println("No possible answers!");
return;
} // if the range is empty.
if (upper > Long.MAX_VALUE/2) {
out.println("The upper bound of the range cannot be higher than " +
Long.MAX_VALUE/2);
return;
} // If the upper bound is too high.
if (lower < Long.MIN_VALUE/2) {
out.println("The lower bound of the range cannot be smaller than " +
Long.MIN_VALUE/2);
return;
}
// Make a guess directly between the two.
long guess = (lower+upper) / 2;
out.println("I guess: " + guess);
// Is it correct?
if (oracle.isCorrect(guess)) {
out.println("Wa hoo! The answer is " + guess);
}
// Is it too small? If so, we know it has to be in the range
// [guess+1 ... upper].
else if (oracle.isSmall(guess)) {
out.println(" Oh well, that guess is too small.");
guessNumber(guess+1,upper,out,oracle);
}
// It's not correct. It's not too small. It must be too large.
// Hence, the number must be in the range [lower ... guess-1].
else {
out.println(" Hmmm. That guess is too large.");
guessNumber(lower,guess-1,out,oracle);
}
} // guessNumber(long,long,SimpleOutput,Oracle)
} // class NumberGameGuesser
What does the oracle that this class uses look like? Basically, it has a field that contains the answer. Each of the methods compares the guess to that answer. The following is the code for that class.
/**
* An oracle for numeric guessing games. You tell the oracle the number,
* and the oracle can answer questions about guesses.
*
* @author Samuel A. Rebelsky
* @version 1.0 of January 1999
*/
public class NumberGameOracle {
// +--------+------------------------------------------------------------
// | Fields |
// +--------+
/** The number we're trying to guess. */
long solution;
// +--------------+------------------------------------------------------
// | Constructors |
// +--------------+
/**
* Create a new oracle who knows that the solution is the given value.
*/
public NumberGameOracle(long solution) {
this.solution = solution;
} // NumberGameOracle
// +---------+-----------------------------------------------------------
// | Methods |
// +---------+
/**
* Check if a guess is correct.
*/
public boolean isCorrect(long guess) {
return guess == solution;
} // isCorrect(long)
/**
* Check if a guess is too small.
*/
public boolean isSmall(long guess) {
return guess < solution;
} // isSmall(long)
/**
* Check if a guess is too large.
*/
public boolean isLarge(long guess) {
return guess > solution;
} // isLarge(long)
} // class NumberGameOracle
We can put these together into a game as follows.
import SimpleOutput;
import SimpleInput;
import NumberGameOracle; // The oracle knows the answer.
import NumberGameGuesser; // The guesser does not.
/**
* Let the computer play the number game. The user tells the computer
* which number, and then the guesser tries to guess.
*
* @author Samuel A. Rebelsky
* @version 1.0 of January 1999
*/
public class NumberGame {
/**
* Play the game.
*/
public static void main(String[] args) {
// A game with no output is fairly boring.
SimpleOutput out = new SimpleOutput();
// We'll need to read a number to guess.
SimpleInput in = new SimpleInput();
// Our intelligent guesser.
NumberGameGuesser guesser = new NumberGameGuesser();
// And our even more intelligent oracle. We'll create the oracle once
// we know the solution.
NumberGameOracle oracle;
// The number to guess.
long solution;
// The lower bound of the range.
long lower;
// The upper bound of the range.
long upper;
// The minimum lower and maximum upper bounds (required by the guesser).
long min_lower = Long.MIN_VALUE/2;
long max_upper = Long.MAX_VALUE/2;
// Describe the game.
out.println("Welcome to the amazing number game. You will give me");
out.println("a range of numbers and a number to guess. I will tell");
out.println("my friend to guess the number, and we'll see how it does.");
out.println();
// Ask for the range.
out.print("Enter the smallest possible answer " +
"(at least " + min_lower + "): ");
lower = in.readLong();
if (in.hadError()) { lower = min_lower; }
out.print("Enter the largest possible answer " +
"(at most " + max_upper + "): ");
upper = in.readLong();
if (in.hadError()) { upper = max_upper; }
// Validate the range.
if (lower < min_lower) {
out.println("Your smallest number is too small.");
return;
}
if (upper > max_upper) {
out.println("Your largest number is too large.");
return;
}
if (upper < lower) {
out.println("The smallest number is larger than the largest number.");
return;
}
// Ask for input.
out.print("Please enter the number to guess: " +
"(between " + lower + " and " + upper + "): ");
solution = in.readLong();
// Validate the solution.
if (solution < lower) {
out.println("Your solution is less than the smallest number.");
return;
}
if (solution > upper) {
out.println("Your solution is larger than the largest number.");
return;
}
// Create the oracle.
oracle = new NumberGameOracle(solution);
// Okay, let's play the game.
guesser.guessNumber(lower,upper,out,oracle);
// We're done.
} // main(String[])
} // class NumberGame
Why do we limit the lower and upper bounds? You'll learn why in our discussion of binary search below. You will investigate the problem further in the post-laboratory problems.
In Experiment A2.4 you will play with this game.
We can turn this strategy into a searching algorithm, as long as the list we are searching is sorted. How could you take advantage of it being sorted? If the sequence is sorted, then you learn a lot about where the name belongs by comparing the name you're looking for to the middle element. For example, if the name you are looking for is smaller than the middle element, then you can throw away everything after the middle element. In effect, you have eliminated half the sequence in one step!
What do we do with the remaining half of the sequence? We search through it again, using the same technique. (Yes, that's recursion in action.) We keep splitting the sequence, again and again, until we find the element we are searching for or end up with no remaining elements.
Expressed in approximate Java, we have
/**
* Determine whether a name appears in a sequence.
*/
public boolean search(String name, Sequence names) {
// A name cannot appear in the empty sequence
if (names.length() == 0) {
return false;
} // empty sequence
// Nonempty sequences: check the middle and recurse
else {
// Is the element at the middle?
if (name.equals(names.middle())) {
return true;
} // at the middle
// Is the element before the middle?
else if (name.precedes(names.middle())) {
return search(name, names.firstHalf());
} // In the first half
// Otherwise, look in the second half
else {
return search(name, names.secondHalf());
} // In the first half
} // search(String,Sequence)
Note that this is not a working method. In particular, there is no
precedes method for strings, nor a built-in
Sequence class. In addition, binary search requires
some care at the extremes (e.g., single-element lists) to ensure
that it does not recurse indefinitely. However, this code should
give you a sense that recursion provides an elegant way to solve
a variety of problems. In fact, the problem-solving technique used
in binary search is so common that it has its own name,
divide-and-conquer.
Working code for the preceding method follows. The code is part of the
IntSeq class, which uses this.elements as
the array it searches through. This implementation of the method also
returns the index of the element, rather than a boolean value indicating
whether or not it is found.
/**
* Search through the elements for a particular value.
* Return the index of the value if it is found.
* Return -1 otherwise.
*/
public int binarySearch(int val) {
return binarySearch(val, arr, 0, this.elements.length-1);
} // binarySearch(int)
/**
* Search for a value in a subrange of the array.
* The subarray is given by lb .. ub.
* Return the index of the value if it is found.
* Return -1 otherwise.
*/
protected int binarySearch(int val, int lb, int ub) {
// The index of the middle value
int mid = (lb + ub) / 2;
// Is the subarray empty?
if (lb > ub) {
return -1;
} // empty subarray
// Is the value at the middle?
else if (val == this.elements[mid]) {
return mid;
} // Found it!
// Should the value be in the left half?
else if (val < this.elements[mid]) {
return binarySearch(val, lb, mid-1);
} // left half
// The value must be in the right half.
return binarySearch(val, mid+1, ub);
} // left half
} // binarySearch(int,int,int)
Although binary search is a popular and useful algorithm, many programmers end up making mistakes when they implement it, even if they've been warned that they are likely to make mistakes. What kinds of mistakes? Most are relatively subtle, but almost all can lead to significant problems in practice.
Some programmers forget to ensure that the array they're searching is nonempty. This means that when they look at the ``middle'' element, they are looking at a nonexistent element. In Java, this oversight will lead to an error at the time the attempt to access the element happens. In other languages, no error may be noticed until later.
Some programmers include the midpoint in the recursive call (using [small .. midpoint] or [midpoint .. large] rather than [small .. midpoint-1] or [midpoint+1 .. large]. While this usually works, in some cases it can lead to problems. For example, consider the case in which the element is at position 3, small is 2, and large is 3. The midpoint is 2 (Java rounds down when dividing integers). The element at position 2 is too small, so we try again, using small=middle and large=large. So, small is 2 and large is 3. The midpoint is 2. The element at position 2 is too small, so we try again. And so on and so forth.
Some programmers try to reduce the number of tests so that, for example, there are not separate tests for less-than and equals. While this can be done successfully, it may have the problem mentioned with including the midpoint in the recursive call.
A more subtle problem comes in the computation of the midpoint. Recall
that the computation uses (lb+ub)/2. Since Java limits
the size of integers, it is possible that lb+ub will be
greater than the largest integer. In fact, this is why
NumberGameGuesser limits the range to half of the two
bounds. This problem is rarely encountered in practice, but is worth
considering as data sets get larger and larger.
In Experiment A2.6, you will investigate some of these problems.
In the previous examples, we've known what we were searching for (e.g., Is this number in this sequence?). There are related problems in which we have less information about what we are searching for. For example, consider the problem of searching for the smallest element of a sequence. How might you find such an element? A first guess might be the first element, but that's often an incorrect guess. You might then refine your guess by then stepping through the remaining elements, updating your estimate of the smallest whenever you found a smaller element. In pseudocode,
guess = the first element of the sequence
for each remaining element of the sequence, e
if (e < guess) then
guess = e;
end if
end for
Using arrays in Java, we might express this as follows.
/**
* Compute the smallest element in the sequence.
*/
public int smallest() {
// Our guess as to the smallest element
int guess = this.elements[0];
// A counter variable
int i;
// Look through all subsequent elements
for (i = 1; i < this.elements.length; ++i) {
// If the element is smaller than our guess, then
// update the guess
if (this.elements[i] < guess) {
guess = this.elements[i];
} // if
} // for
// That's it, we're done
return guess;
} // smallest()
As a variation, we might write an indexOfSmallest that
returns the index of the smallest element in a subsequence? Why
would we want such a method? As you've seen, whenever your write a
method for a sequence, it is helpful to write a similar method for
a subsequence. Why return an index rather than the actual value?
Because it will be helpful for the subsequent experiments.
The following is the method as it appears in the IntSeq
class.
/**
* Compute the index of the smallest element in the subsequence
* given by lower bound lb and upper bound ub.
*/
public int indexOfSmallest(int lb, int ub) {
// Make sure the upper bound and lower bound are reasonable.
if (lb < 0) {
lb = 0;
}
if (ub >= this.elements.length) {
ub = this.elements.length - 1;
}
// Our guess as to the index of the smallest element
int guess = lb;
// A counter variable
int i;
// Look through all subsequent elements
for (i = lb + 1; i <= ub; ++i) {
// If the element is smaller than our guess, then
// update the guess
if (this.elements[i] < this.elements[guess]) {
guess = i;
} // if
} // for
// That's it, we're done
return guess;
} // indexOfSmallest()
Required files:
Step 1.
Make copies of IntSeq.java and IntSeqTester.java.
Write a summary of the methods provided by IntSeq. You need
not read the code for the methods; simply read the introductory comments
(and perhaps the internal comments) to gain an understanding of what they
might do.
Step 2.
Compile IntSeq and IntSeqTester.
Execute IntSeqTester.
Ask the tester to fill the elements between
0 and 10 with the sequence starting with 1 and stepping by 2. Print out
that sequence. Record the results.
Step 3.
Execute IntSeqTester.
Ask the tester to fill the elements between
5 and 10 with the sequence starting with 1 and stepping by -2. Print out
that sequence. Record the results.
Step 4.
Execute IntSeqTester.
Ask the tester to fill the elements between
0 and 10 with the sequence starting with 5 and stepping by 0. Print out
that sequence. Record the results.
Step 5. What command(s) might you use to create the sequence [1,3,5,7,9,...,301]? What command(s) might you use to create the sequence [301,299,297,...,5,3,1]?
Step 7.
At times, you need to set elements individually, rather than en masse.
Using IntSeqTester, build and print the sequence [2,1,5,4,-1,6].
(You do not need to record anything for this step.)
Step 8.
Although programs like IntSeqTester provide a simple
and useful mechanism for testing other classes, it is also helpful
to be able to write small programs that do more explicit tests.
Write a small program, SampleSeq that builds and prints
the sequence [2,1,5,4,-1,6]. Summarize your code here.
Required files:
Step 1.
Make copies of IntSeq.java and IntSeqTester.java.
Compile the two files. Using SortTester, make five lists of ten
random numbers. Record those lists.
Step 2.
Using IntSeqTester, make three lists of ten random numbers,
using the same seed each time (do not use zero as your seed). Record
your results.
Step 3.
Using IntSeqTester, make the following lists of random
numbers using the same seed each time. Note that the r
entries stand for ``some random number''.
r,r,r,r,r 0,r,r,r,r 0,0,r,r,r 0,0,0,r,r 0,0,0,0,r
Record the results.
Step 4. Based on those results, what can you say about seeds?
Required files:
Step 1.
Make a copy of IntSeq.java and IntSeqTester.
Compile the two classes and execute IntSeqTester. Create
the list [1,2,3,4,5]. Using sequential search, determine the index of 1, the
index of 5, and the index of 20.
Step 2.
Execute IntSeqTester. Create the list [1,1,1,2,2,2,3,3,3].
Using sequential search, determine the index of 1, 2, and 3.
Step 3. What, if anything, do you observe from the previous step?
Step 4.
Execute IntSeqTester. Create a sequence of 1000 elements.
Does 0 appear in that sequence? How likely do you think it is that 0 will
appear in the sequence?
Required files:
Before you begin,
make copies of
NumberGame.java,
NumberGameOracle.java,
and
NumberGameGuesser.java.
Compile the three classes.
Step 1.
Execute NumberGame.
What numbers does the guesser guess when searching for 6 in the range [0..100]?
Step 2.
Execute NumberGame. What numbers does the guesser guess when
searching for -6 in the range [-100..0]?
Step 3.
Execute NumberGame. What numbers does the guesser guess when
searching for 101 in the range [-100..100]?
Step 4.
Execute NumberGame. What numbers does the guesser guess
when searching for 100 in the range [-100..100]?
Step 5.
Update NumberGameGuesser so that it reports on the number
of guesses that it takes to find a solution. Summarize your changes here.
Step 6.
Execute NumberGame. How many guesses does it take to look
for 511231 when searching in the range [0..1000000]?
Step 7. How many guesses does it take to find 0 in the full range? Note that you can just type carriage return when prompted for lower and upper bounds to get the specified bounds. How many guesses does it take to find 1? How many guesses to find 1000000?
Step 8. What is the largest number of guesses that it takes to find a number in the full range? What number requires that many guesses?
Step 9. How did you determine your answer to the previous step?
Step 1. Consider the array of the first sixteen integers, [2,4,...,32]. What elements would binary search look at in determining whether 16 is in the array? Note that Java rounds down when dividing integers.
Step 2.
Create a new class, SearchTester, with a
main method that contains the following lines.
// Prepare for reading input and generating output.
SimpleInput in = new SimpleInput();
SimpleOutput out = new SimpleOutput();
// Prepare our sequence.
IntSeq seq = new IntSeq();
// The value we're looking for
int val;
// The position of that value
int pos;
// Fill the sequence with the even numbers from 2 to 32.
seq.fill(0,15,2,2);
// Read a value and determine its position.
out.print("Search for what value? ");
val = in.readInt();
// Search for the value.
pos = seq.binarySearch(val);
if (pos == -1) {
out.println(val + " is not in the first sixteen even numbers");
} // invalid position
else {
out.println(val + " falls at position " + pos);
} // valid position
Compile and execute SearchTester. How many steps does it
take to determine whether 16 is in the array? 12? 1? 15? 0? Do the
answers correspond to your answers from the previous step? If not, can
you guess why not?
Step 3.
What happens when binary search is used on an unsorted list? Update
SearchTester to build the sequence [5,1,3,7,2,8,0].
Search for 8, 1, 5, and 2. Which does it get correct? How many steps
does it take in each case? Explain.
Step 4.
Suppose we were interested in more details on the steps used in binary
search.
Add methods to IntSeq that do binary search and also print
the steps involved in binary search. The two methods should be
binarySearch(SimpleOutput out, int val) and
binarySearch(SimpleOutput out, int val, int lb, int ub)
For example, in searching for 4 in [1,3,5,7,9,11,13], the output might be
Looking for 4 in positions 0 to 6 The middle element (position 3) is 7. 4 < 7: Throwing away elements at positions 3 to 6 Looking for 4 in positions 0 to 2 The middle element (position 1) is 3. 4 > 3: Throwing away elements at position 0 to 1 Looking for 4 in positions 1 to 2. The middle element (position 2) is 5. 4 < 5: Throwing away elements at position 2 There are no elements remaining. 4 is not in the array.
You need not record anything for this step.
Step 5.
Using your modified IntSeq, redo step 3 and explain the
results.
Step 6.
We have not considered what binary search does when the same element
appears multiple times in a list. Update SearchTester
to determine which version of each number is found in
[1,1,1,2,2,2,3,3,3]. Summarize your results.
Required files:
IntSeq.java, as modified in the previous experiment
to report on positions in binary search.
SearchTester.java, created in the previous experiment.
Before you begin,
if you have not modified IntSeq.java to print the steps
used in binary search, here are the appropriate methods to add.
/**
* Search through a sorted array of integers for a particular value.
* Print the steps as you go.
* Return the index of the value if it is found.
* Return -1 otherwise.
*/
public int binarySearch(SimpleOutput out, int val) {
return binarySearch(out, val, 0, this.elements.length-1);
} // binarySearch(int)
/**
* Search for a value in a subarray of a sorted array of integers.
* The subarray is given by lb .. ub.
* Return the index of the value if it is found.
* Return -1 otherwise.
*/
protected int binarySearch(SimpleOutput out, int val, int lb, int ub) {
// Compute the index of the middle value.
int mid = (lb + ub) / 2;
// Print some feedback.
out.println("Looking for " + val + " in positions " + lb + " to " + ub);
if (mid > 0) {
out.println(" The middle element (position " + mid + ") is " +
this.elements[mid]);
}
// Is the subarray empty?
if (lb > ub) {
out.println(" There are no elements remaining.");
out.println(val + " is not in the array");
return -1;
} // empty subarray
// Is the value at the middle?
else if (val == this.elements[mid]) {
return mid;
} // Found it!
// Should the value be in the left half?
else if (val < this.elements[mid]) {
// Give feedback.
out.println(" " + val + " < " + this.elements[mid] +
": Throwing away elements at positions " +
mid + " to " + ub);
// And recurse.
return binarySearch(out, val, lb, mid-1);
} // left half
// The value must be in the right half.
else {
// Give feedback.
out.println(" " + val + " > " + this.elements[mid] +
": Throwing away elements at positions " +
lb + " to " + mid);
// And recurse
return binarySearch(out, val, mid+1, ub);
} // right half
} // binarySearch(SimpleOutput, int, int, int)
Step 1.
Using SearchTester, record
the steps used to search for 1,2,3, and 4 in the array [2,4,6,8]
using binary search.
Step 2.
Using SearchTester, record
the steps used to search for 1,2,3, and 4 in the array [2,4]
using binary search.
Step 3.
Modify binarySearch so that it includes the midpoint
in the recursive calls. These new recursive calls should resemble
return binarySearch(out, val, lb, mid);
...
return binarySearch(out, val, mid, ub);
(Note that the extra parameter was included when you added support for printing the steps.)
Step 4.
Using SearchTester, record
the steps used to search for 1,2,3, and 4 in the array [2,4,6,8]
using the modified binary search.
Step 5.
Using SearchTester, record
the steps used to search for 1,2,3, and 4 in the array [2,4]
using the modified binary search.
Step 6. What do these results suggest?
Rewrite the binary search given in
IntSeq.java iteratively;
that is, use loops rather than recursive calls.
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.
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.
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.
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.
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?
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.
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.
[Front Door] [Introduction] [Code]
Copyright (c) 1998 Samuel A. Rebelsky. All rights reserved.
Source text last modified Wed Oct 6 12:39:49 1999.
This page generated on Tue Oct 26 15:40:36 1999 by Siteweaver.
Contact our webmaster at rebelsky@math.grin.edu