Binary Search and Correctness
Due: Feb 27, 2012

Presentation By: XXX and YYY

Your mission for Homework #5 is to implement a binary search. However, in this problem, your sorted data is on disk. For Example, you might create data that looks like the following:

005 NY Mid-Island....
006 PR San Juan......
007 PR San Juan......
008 VI Virgin Islands
009 PR San Juan......
...
995 AK Anchorage.....
996 AK Anchorage.....
997 AK Fairbanks.....
998 AK Juneau........
999 AK Ketchikan.....

Notice that each dot on the end of a line is a space. That makes it so that each line is exactly the same length.

You goal is to write a function that given a item to look up (say "467") you will perform a binary search on this data to either find the row, or report that no such data exist. DO NOT READ THE WHOLE DATA FILE INTO MEMORY!

You will need:

1. to create a large file of data, like above. Should be in order of the first elements. The bigger the better!
2. to know the size of the file (have your program figure it out)
3. to know how many characters are on each line (have your program measure the first line, and assume they are all the same length)
4. how to move to a particular place in the file
5. a binary search to find the key
6. Your code should have checks to verify that it is correct
7. ask user for filename and key to find (and use command-line args)
8. report back row of data found, or "Data not found" message
9. tests to show how long it takes finding first, middle, and last keys

What to hand in

1. Code
2. Analysis write-up

Back to CS330 Materials