CS195 2003S : Homework 0: Binary Search

Summary: In this assignment, you will sketch or implement a version of the standard binary search algorithm.

Citation: Much of the problem statement is based on Column 4 of the second edition Jon Bentley's Programming Pearls.

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 or that you've found on the Web. The goal of this assignment is to see how you do implementing binary search from scratch.

Submitting Your Work: Submit your source code with the ECA. If you can't get it to work, email me your source code.

Assignment

Implement (in Scheme, Java, or Pseudocode) the following version of Binary search. If you implement in pseudocode, you should be confident that your algorithm would work if you translated it into a real programming language. If you use Scheme, substitute vector for array in the problem statement.

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)

History

Tuesday, 14 January 2003 [Samuel A. Rebelsky]

Created as a mostly blank template.

Monday, 20 January 2003 [Samuel A. Rebelsky]

Filled in the details.

Primary: [Front Door] [Current] [Glance] - [Blurb] [Disabilities] [Honesty] [Instructions] [Links] [Search] [Syllabus]
Groupings: [EBoards] [Examples] [Exams] [Handouts] [Homework] [Labs] [Outlines] [Readings] [Reference]
ECA: [About] [Grades] [Quizzes] [Submit Work] [Change Password] [Reset Password]
Misc: [Walker/Fall 2001] [SamR]

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri May 2 14:19:32 2003.
The source to the document was last modified on Mon Jan 20 13:16:55 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS195/2003S/Homework/hw.00.html.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu