Theta(lgn + lgm) Search of 2-Dimensional Array

Write a Theta(lgn + lgm) program that searches for a value in a n x m array. The array is sorted along the rows and columns:

• S[i][j] <= S[i][j+1]
• S[i][j] <= S[i+1][j]

Write a main program:

Restriction: You may not use the STL. Your 2D array processing must be your own. The only libraries you may use are iostream, fstream, and cassert.

1. Reads in the name of a file
2. Open the file. Use cassert to ensure the file opened properly.

You can assume all of the data in the file is valid integer data. You must properly handle an empty file.

3. The first two integers in the file are n and m respectively. Read them in. Declare a two-dimensional n x m array (n is the number of rows and m is the number of columns).
4. You can assume the file contains n x m integers in non-decreasing order. You do not have to verify the ordering of the data. Read m x n integers in and fill in the two-dimensional array row by row.
5. Print the contents of the array.
6. The remaining data in the file is the keys to search for. You will then go into a loop reading data in one integer key at a time. Write code that runs in Theta(lgn + lgm) time that searches the n x m array for the key. Your loop will terminate on end of file.
   • Print out the key to be searched for
   • If the key is found, print out the row and column number of the position in which it was found. The indices are 0 based.
   • If the key is not found, print a message stating it was not found.
   Your algorithm must be a theta(lgn + lgm).

Submission

1. Your program must be in a file called search2d.cpp
2. Use turnin to submit your file selecting cs328 search2d
3. Your well documented code is worth 85 points.
4. Write a report and submit it via D2l that makes an valid argument that your program runs in theta(lgn + lgm) time. This is worth 15 points.