Question

JAVA

Write a program which will read a text file into an ArrayList of Strings. Note that the given data file (i.e., “sortedStrings.txt”) contains the words already sorted for your convenience.

• Read a search key word (i.e., string) from the keyboard and use sequential and binary searches to check to see if the string is present as the instance of ArraryList.

• Refer to “SearchInt.java” (given in “SearchString.zip”) and the following UML diagram for the details of required program components (including the class name, data fields, and methods) for this assignment. SearchString +TO_STOP: String +NOT_FOUND: int +count1: int +count2: int +count3:int +sequentialSearch (array: ArrayList<String>, value: String): int +binarySearch(array: ArrayList<String>, value: String): int +binarySearch(array: ArrayList<String>, low: int, high:int, value: String): int +main(args: String[]): void +main(): void

• HINTS & STEPS:

(H1) Declare the two symbolic constants as public, static, and final. To be more specific, declare them as follows: public static final String TO_STOP = “-1”; and public static final int NOT_FOUND = -1;

(H2) Declare count1, count2, and count3 as static, each of which keeps track of number of comparison operations in sequentialSearch(), iterative binarySearch(), and recursive binarySearch(), respectively.

(H3) binarySearch(array: ArrayList<String>, value: String) is the header for iterative binary search method and binarySearch(array: ArrayList<String>, low: int, high: int, value: String) is the header for recursive binary search method.

(H4) Every search method should be written a separate method, which returns the index in the instance of ArrayList if the search key word exists, or returns -1(i.e., NOT_FOUND) if the search key word doesn’t exist.

(H5) First, declare all the first four methods (i.e., sequentialSearch(), the two binarySearch()s, and main()) to be static (i.e., static(=class) methods) and complete the remaining program accordingly. After you confirm that your program works properly as shown in the running example,declare the first three methods (sequentialSearch() and the two binarySearch()s) to be non-static (i.e., non-static(=instance) methods, commenting out the corresponding method headers. What do you need to change in your static main() if you want to use the non-static(=instance) methods. Briefly discuss (or explain) this in your program file.
COSC 1437 Programming Assignment page 2 of 2

(H6) Declare the fifth method (i.e., main()) as a non-static (i.e., instance) method in “SearchString.java”. Notice that this non-static main() does not have parameters and thus this main() is different from the static main(String[] args) in terms of using a different modifier as well as a different signature. By the way, is it fine to declare main() like this? If yes, what are you practicing now with this? Overloading or overriding? Otherwise, explain why it is not valid.

(H7) Implement a driver class (say “TestSearchString.java”) and show how to use/call the methods in “SearchString.java” to get the same output shown as running example below. Briefly discuss (or explain) how to call static(=class) methods and non-static(=instance) methods in “SearchString.java” from the driver (“TestSearchString.java”). TestSearchString

+main(args: String[]): void

(H8) What do you need to change if you change the access modifier from public to private after step (H7) for all the constants and variables in the data field? How about if you change all the occurrence of public (i.e, both in data field and each method header) as private? Were you able to run your program either in SearchString.java or in TestSearchString.java? (H9) What if you don’t have the two main()s in SearchString class. What do you need to change in main() in TestSearchString class to get the exactly same result you get at step (H7) with either all public data fields or all private data fields?

Answer 1

If you have any doubts, please give me comment...

import java.io.*;

import java.util.ArrayList;

import java.util.Scanner;

import java.lang.Integer;

public class SearchString {

    public static final String TO_STOP = "-1";

    public static final int NOT_FOUND = -1;

    public static final int MAX_SIZE = 10000;

    public static int count1;

    public static int count2;

    public static int count3;

    public int sequentialSearch(ArrayList<String> array, String value) {

        int low = 0;

        int high = array.size() - 1;

        for (int i = low; i <= high; i++) {

            count1++;

            if (array.get(i).equals(value))

                return i;

        }

        return NOT_FOUND;

    } // end of sequentialSearch()

    public int binarySearch(ArrayList<String> array, String value) {

        int low = 0;

        int high = array.size() - 1;

        while (low <= high) {

            int mid = (low + high) / 2;

            count2++;

            if (array.get(mid).compareTo(value) > 0) {

                high = mid - 1;

            } else if (array.get(mid).compareTo(value) < 0) {

                low = mid + 1;

            } else

                return mid;

        }

        return NOT_FOUND;

    } // end of binarySearch()

    public int binarySearch(ArrayList<String> array, int low, int high, String value) {

        if (low > high)

            return NOT_FOUND;

        int mid = (low + high) / 2;

        count3++;

        if (array.get(mid).compareTo(value) > 0) {

            return binarySearch(array, low, mid - 1, value);

        } else if (array.get(mid).compareTo(value) < 0) {

            return binarySearch(array, mid + 1, high, value);

        } else

            return mid;

    } // end of binarySearch()

    public static void main(String[] args) throws IOException {

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

        String filename;

        Scanner keyboard = new Scanner(System.in);

        System.out.print("Type the filename to read: ");

        filename = keyboard.nextLine();

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

        while (fileScnr.hasNext())

            list.add(fileScnr.next());

        fileScnr.close();

        System.out.println(list.size() + " words are populated in the instance of ArrayList.");

        boolean wantToContinue = true;

        SearchString si = new SearchString();

        do {

            System.out.print("Type a word to search (" + TO_STOP + " to stop): ");

            String word2Search = keyboard.nextLine();

            if (word2Search.equals(TO_STOP)) {

                wantToContinue = false;

            } else {

                count1 = count2 = count3 = 0;

                int index;

                index = si.sequentialSearch(list, word2Search);

                if (index == NOT_FOUND)

                    System.out.println(

                            "sequentialSearch()      : " + word2Search + " is not found (comparison=" + count1 + ").");

                else

                    System.out.println("sequentialSearch()      : " + word2Search + " is found in [" + index

                            + "] (comparison=" + count1 + ").");

                index = si.binarySearch(list, word2Search);

                if (index == NOT_FOUND)

                    System.out.println(

                            "iterative binarySearch(): " + word2Search + " is not found (comparison=" + count2 + ").");

                else

                    System.out.println("iterative binarySearch(): " + word2Search + " is found in [" + index

                            + "] (comparison=" + count2 + ").");

                index = si.binarySearch(list, 0, list.size() - 1, word2Search);

                if (index == NOT_FOUND)

                    System.out.println(

                            "recursive binarySearch(): " + word2Search + " is not found (comparison=" + count3 + ").");

                else

                    System.out.println("recursive binarySearch(): " + word2Search + " is found in [" + index

                            + "] (comparison=" + count3 + ").");

            }

        } while (wantToContinue);

        keyboard.close();

    } // end of main()

} // end of TestSearch