代写Binary Search和Merge Sort两个算法。
Requirement
In this assignment you will implement the Binary Search and Merge Sort
algorithms discussed in class. You may begin by studying the examples posted
on the webpage.
Your task will be to adapt these methods to operate on String arrays rather
than int arrays. The key operation to alter is the comparison of array
elements. Given Strings s1 and s2, the expression s1.compareTo(s2)<0
returns true if and only if s1<s2 in the lexical ordering induced by the
Unicode Character Set, s1.compareTo(s2)==0 if and only if the Strings are
identical, and s1.compareTo(s2)>0 if and only if s1>s2 in the same
ordering. Go through the Binary Search and Merge Sort examples and replace int
comparison with String comparison where appropriate. You will write a program
called Search.java that takes command line arguments giving a file to be
searched and target word(s) to search for. The executable jar file will be
named Search so the command line will look like:
% Search file target1 [target2 target3 ..]
As always % represents the Unix prompt. The items in brackets [] represent
optional arguments.
Input File Format and Program Output
Each line of the input file for this project will contain a single word, i.e.
a string containing no spaces or tabs. Your program will determine whether or
not the target word is amongst the words in the input file, print a message to
stdout stating whether or not the target was found, and (optionally) state the
line on which the target was found, if it is found. You may assume that your
program will be tested only on properly formatted input files. For example
suppose file1 contains the following lines:
entire
beginning
possibly
specified
key
value
initial
before
dictionary
however
Running the program on file1 with several targets results in:
% Search
Usage: Search file target1 [target2 ..]
% Search file1 key happy dictionary
key found on line 5
happy not found
dictionary found on line 9
Observe that line numbering starts at 1. If you choose the option to not
report where the target is found, the corresponding output would be:
% Search file1 key happy dictionary
key found
happy not found
dictionary found
Actually this is not an option if you aspire to get an A or better on this
assignment. In other words if your program does not state the line on which
target is found, your maximum possible score will be 90 out of 100 (which is
A-). The functionality you choose to implement must be clearly stated in your
README file. It is recommended that you begin by completing the project
without reporting the line number where the target is found, submit your
project, then start working on the additional functionality.
Program Operation
Your program should begin by determining the number of lines in the input
file. See the examples LineCount.java and LC.java on the webpage.
To see some ways to do this. If the number of lines (and therefore the number
of words) is n, allocate a String array of length n and scan the file again,
storing each word in the array. Your program will use Binary Search to find
the target word(s). Recall however that Binary Search requires the array to be
in increasing order. As the above example indicates though, you cannot expect
the input file to be sorted. Therefore you must first call Merge Sort on the
array before you search it. Binary Search returns -1 if the target is not
found, and a non-negative integer giving it’s index in the array if it is
found. You can simply test this return value to determine if the target was
found. Unfortunately the index returned by Binary Search is not the original
index of the target in the unsorted array, which is what you need to determine
the position of the target in the input file.
This is only a problem if you are choosing the more ambitious option of
reporting the line on which the target is found. A tempting approach to
overcome the problem is to simply do a linear search of the word array for the
target. This would actually be the simplest way to write a program that
transforms the input into the required output. However this is not the task
before you and not the point of the exercise. You must sort the word array
using Merge Sort, then search it using Binary Search, which you’ll recall is
more efficient than a linear search. To determine the line number on which the
target is found, alter the mergeSort() method so as to pass in an int array
that keeps track of the line number for each of the words in the array being
sorted. Likewise, the merge() method should also pass such an array. The
signatures of mergeSort() and merge() would then be:
static void mergeSort(String[] word, int[] lineNumber, int p, int r)
static void merge(String[] word, int[] lineNumber, int p, int q, int r)
—|—
Recall from our discussion in class that merge()is where the real work of
mergeSort() is done. When a call to mergeSort() returns, lineNumber[k] should
be the line number where word[k] is located in the input file. For instance:
String[] word = {“ccc”, “bbb”, “ddd”, “aaa”};
int[] lineNumber = {1, 2, 3, 4};
mergeSort(word, lineNumber, 0, 3);
// now:
// word is {“aaa”, “bbb”, “ccc”, “ddd”}
// lineNumber is {4, 2, 1, 3}
—|—
Think of the sorting action as performing a permutation of the input array
that places it in a certain order. The trick is to write mergeSort() and
merge() so as to perform the same permutation on the subarray lineNumber[p….r]
as is performed on subarray word[p….r]. Actually mergeSort() will just pass
this problem along to merge(), which as usual, is where the real work is done.
See the project description for lab2 to learn how to deal with command line
arguments and file input. It is recommended that you begin your project by
manually initializing a String array in function main(), write functions
mergeSort() and merge() to sort that array, adapt function main() to read a
file given on the command line, then work on getting the output to display
line numbers of found targets.
What to turn in
Submit the files README, Makefile, and Search.java. Your Makefile must create
an executable jar file called Search, and must include a clean utility that
removes all .class files as well as Search itself. See Lab Assignment 1 to
learn how to do this. Submit all files to the assignment name pa2.
