Goal Build three search algorithms to find matching names in two different lists using Java….

import java.io.File;

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.util.ArrayList;

import java.util.Scanner;

public class SearchAlgorithms {

//loads the contents specified file into and an arraylist and returns the list

private static ArrayList<String> loadFile(String filename) throws FileNotFoundException

{

Scanner scanner = new Scanner(new File(filename));

ArrayList<String> list = new ArrayList<String>();

while(scanner.hasNext())

{

String str = scanner.next();

list.add(str);

}

scanner.close();

return list;

}

// words from list2 are searched in list1 using linear search algorithm. words that

//were found in are printed into writer object

private static void findByBruteForce(ArrayList<String> list1, ArrayList<String> list2,PrintWriter writer)

{

String search;

boolean found;

writer.write(“nThe method findByBruteForce found the following match(es):n”);

for(int i = 0; i < list2.size()-1; ++i) //loop through list2

{

search = list2.get(i);

found = false;

//search the word in list1 linearly

for(int j = 0; j < list1.size() && !found; ++j)

{

if(list1.get(j).equals(search))

found = true;

}

//if found , write into writer

if(found)

writer.write(search+”n”);

}

}

// words from list2 are searched in list1 using binary search algorithm. words that

//were found in are printed into writer object

private static void findByBinarySearch(ArrayList<String> list1, ArrayList<String> list2,PrintWriter writer)

{

String search;

boolean found;

int start, end, mid, cmp;

writer.write(“nThe method findByBinarySearch found the following match(es):n”);

for(int i = 0; i < list2.size(); ++i) //loop through words in list2

{

search = list2.get(i);

//reset all variables

found = false;

start = 0;

end = list1.size()-1;

while(!found && start <= end)

{

mid = (start + end)/2;

cmp = search.compareTo(list1.get(mid));

if(cmp == 0)

found=true;

else if(cmp < 0 )

end = mid – 1;

else

start = mid + 1;

}

if(found) //write to writer if found

writer.write(search+”n”);

}

}

// words from list2 are searched in list1 using Finesse method. words that

//were found in are printed into writer object

private static void findByFinesse(ArrayList<String> list1, ArrayList<String> list2,PrintWriter writer)

{

writer.write(“nThe method findByFinesse found the following match(es):n”);

int idx1 = 0, idx2 =0;

String word1, word2;

int cmp;

while(idx1 < list1.size() && idx2 < list2.size())

{

word1 = list1.get(idx1);

word2 = list2.get(idx2);

cmp = word1.compareTo(word2);

if(cmp == 0) //words matched

{

writer.write(word1);

idx1++;

idx2++;

}

else if(cmp < 0) //word1 is alphabetically before word2

idx1++;

else //word2 is alphabetically before word1

idx2++;

}

}

public static void main(String[] args) {

try {

//load the files into 2 lists

ArrayList<String> list1 = loadFile(“list1.txt”);

ArrayList<String> list2 = loadFile(“list2.txt”);

//writer for output file

PrintWriter writer = new PrintWriter(new File(“output.txt”));

findByBruteForce(list1, list2, writer);

findByBinarySearch(list1, list2, writer);

findByFinesse(list1, list2, writer);

writer.close();

} catch (FileNotFoundException e) {

System.out.println(e.getMessage());

}

}

}

input file list1.txt

Akira

Bart

Chase

Declan

Duffman

input file list2.txt

Atkins

Blinky

Carl

Duffman

Lisa

output file output.txt

The method findByBruteForce found the following match(es):

Duffman

The method findByBinarySearch found the following match(es):

Duffman

The method findByFinesse found the following match(es):

Duffman