Summary: In this assignment, you will
implement a version of the standard binary search algorithm.
Assigned: Tuesday, 21 January 2003.
Due: noon, Wednesday, 22 January 2003.
Citation:
Much of the problem statement is based on Column 4 of the second edition
Jon Bentley's Programming Pearls.
Bentley, Jon (2000). Programming Pearls, 2nd Edition.
Reading, MA: Addison-Wesley.
Collaboration: You may certainly discuss the assignment
with other students. However, each student should turn in his or her own
solution. Once you've started to write code, you may not show your code
to others.
Reuse: Please do not reuse code you've written previously
(except for homework 0)
or that you've found on the Web. The goal of this assignment is to see how
you do implementing binary search from scratch
.
Formatting Guidelines:
- Include an introductory comment that gives your name and any
instructions for running your program. If you write in Java, you should
use Javadoc-style comments.
- Comment each procedure you write.
- No line should have more than eighty characters.
- Use a reasonable indentation style that reflects the structure
of the program.
- In Java, avoid code that follows an open brace on the same line.
Submitting Your Work: Submit your source code with the
ECA. If you can't get it to
work, email me your source code.
Implement (in Scheme or Java) the following version of Binary search.
If you use Scheme, substitute vector
for array
in the
problem statement.
Reflect on the errors discussed in class and then perform enough analysis
and testing that you are confident that your binary search is correct.
I'd appreciate it if you showed me your testing steps.
Note that the standard way to keep track of a range
within an array
is with two integer values, one of which gives the lower bound of the
range and the other of which gives the upper bound (both inclusive). You
can use l and u, lb and ub, lower and
upper, lower_index and upper_index, or any other
reasonable pair of names for those two values.
| Procedure |
binary_search |
| Parameters |
n, an integer
x, a sorted array of integers indexed from 0 to n-1
t, an integer
|
| Purpose |
Determine if t appears in x. |
| Produces |
p, an integer |
| Preconditions |
x is sorted in increasing order. That is,
x[i] <= x[i+1] for all reasonable
i.
n >= 0.
|
| Postconditions |
If t appears in x, x[p] = t.
If t does not appear in x, p = -1.
|
| Process |
Keep track of the range within the array that holds t (if
t is anywhere in the array). Initially, the range is the
entire array. The range is shrunk by comparing its middle element
to t and discarding half the range. The process continues
until t is found or until the range in which it must lie is
known to be empty. (Bentley 2000, p. 34) |
Tuesday, 21 January 2003 [Samuel A. Rebelsky]
;
Check with Bobby