Goodnight I need help with this assignment: 1.Build three search algorithms to f

Question

Goodnight I need help with this assignment:

1.Build three search algorithms to find matching names in two different lists in JAVA

2.Read two input files, each containing a sorted list of first names. Assume the input files will be in the working directory and will be named list1.txt and list2.txt.

Find the matching names using three different algorithms. The first list could be considered the reference list, and the second list would contain the list of names to be found.

(a) The first search method, named findByBruteForce should use a linear search of the target list. The inputs to this function will be the two lists.

(b) The second search method, named findByBinarySearch should implement a binary search algorithm. The inputs to this function will be the two lists.

(c) The third search method, named findByFinesse should implement the tokenized search discussed in class and summarized below.

• Start two markers, one for each list, at the beginning of each list. • Repeat the process outlined below

– Compare the two marked items

– If both are equal print the name and advance both markers one element.

– else since they’re not equal advance the marker that comes first, alpha- betically.

3. Testing

There are three files supplied with the assignment:

list1.txt which contains the list of five names.

Akira

Bart

Chase

Declan

Duffman

list2.txt also contains a list of five names.

Duffman

Lisa

expectedOutput.txt which is a redirection of the output. This is to be used as the baseline for running the diff command to confirm the output results and formatting. (See the Sample Output below for an example of how diff will be used.)

Sample output

Duffman

Lisa

Note The diff command will report any differences between the input files. No output means there is no differences between the input files.

Explanation / Answer

Solution:

Note: Tokenized search details not given

package matching;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Matching {
public static void findByBruteForce( ArrayList<String> l1, ArrayList<String> l2)
{
boolean found=false;
System.out.println("The method findByBruteForce found the following match(es):");
for(int k=0;k<l1.size();k++)
{
found=false;
for(int l=0;l<l2.size();l++)
{
if(l1.get(k).equals(l2.get(l)))
{
found=true;
break;
}
}
if(found)
System.out.println(l1.get(k));
}
}
public static void findByBinarySearch( ArrayList<String> l1, ArrayList<String> l2)
{
boolean found=false;
System.out.println("The method findByBinarySearch found the following match(es):");
  
int fir,las,mid;
for(int k=0;k<l1.size();k++)
{
fir=0;
las=l2.size()-1;
mid = (fir + las)/2;
while( fir <= las )
{
if ( l2.get(mid).compareTo(l1.get(k))<0)
fir = mid + 1;
else if (l2.get(mid).equals(l1.get(k)) )
{
System.out.println(l1.get(k));
break;
}
else
las = mid - 1;
mid = (fir + las)/2;   
}
}
}
public static void main(String[] args) throws FileNotFoundException {
Scanner s = new Scanner(new File("list1.txt"));
ArrayList<String> l1 = new ArrayList<String>();
while (s.hasNext()){
l1.add(s.next());
}
s.close();
s = new Scanner(new File("list2.txt"));
ArrayList<String> l2 = new ArrayList<String>();
while (s.hasNext()){
l2.add(s.next());
}
s.close();
findByBruteForce(l1,l2);
findByBinarySearch(l1,l2);
}
  
}

Output:

run:
The method findByBruteForce found the following match(es):
Duffman
The method findByBinarySearch found the following match(es):
Duffman
BUILD SUCCESSFUL (total time: 0 seconds)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.