Code the following as specified: Use the Searcher.java code from Doc Sharing as

Question

Code the following as specified:

Use the Searcher.java code from Doc Sharing as a starting point.

Create an unordered list of 10 String values (you can code this in the main method of Searcher.java). Fill the list with your favorite movies, artists, or songs – but do NOT do this interactively (i.e. do not use a Scanner object for input)

Print the list to make sure it is NOT sorted (Arrays.toString(myList))

Add counting logic to determine the number of times (iterations) each search loop executes.

Execute (call) the linear search method 3 times as you search for the following values and verify the number of iterations:

an item that should be near the beginning if the list were sorted

an item that should be near the end if the list were sorted

An item not in your list

Sort your list (Arrays.sort(myList))

Print the list to make sure it IS sorted (Arrays.toString(myList))

Execute the same 3 linear searches and compare the number of iterations. Are they different, and if so, why are they different?

Execute a binary search for those same 3 items. How are the number of comparisons different for the binary search?

Be sure to label your output so we know which values you were looking for and how many times the search iterated to find that value.

Explanation / Answer

package myProject;

//Class Searcher Definition
public class Searcher
{
   //Main method
   public static void main(String ss[])
   {
       //Creates a list of type string
       String [] myList = new String []{"Dil", "Barsat", "Asique", "City", "Chalbaj", "Danger", "Nastik", "Love", "Noise", "Rang"};                  
       System.out.println("List Not Sorted:");
       //Calls the method to displays unsorted list
       disp(myList);
       System.out.println(" Linear search");
       //Calls the linearSearch method to search a string and display number of iteration required
       System.out.println("Number of Iteration required for first item: " + linearSearch(myList, "Asique"));
       System.out.println("Number of Iteration required for for last item: " + linearSearch(myList, "Rang"));
       //Sorts the list
       sort(myList);  
       //Displays the sorted list
       System.out.println("After Sorted: ");
       disp(myList);
       //Calls the binarySearch method to search a string and displays number of iteration required
       System.out.println(" Binary search");
       System.out.println("Number of Iteration required for first item: " + binarySearch(myList, "Asique"));
       System.out.println("Number of Iteration required for for last item: " + binarySearch(myList, "Rang"));
   }//End of main
  
   //binarySearch method to search a string and displays number of iteration required
   static int binarySearch(String myList[], String st)
   {
       int Beg, Flag, End, Mid = 0, count = 0;
       Beg = Flag = 0;
       End = 10 - 1;
       //Loops till beginning is less than or equals to end
       while(Beg <= End)
       {
           //Calculates the mid
           Mid = (Beg + End) / 2;
           //Increase the counter
           count++;
           //Checks mid position value with the searched string
           if(st.equals(myList[Mid]))
       {
               //Set the flag to 1 and come out of the loop
       Flag = 1;
       break;
       }
           //If the mid position value is less than the compared string change the end to mid value - 1
       else if(st.compareTo(myList[Mid]) < 0 )
           End = Mid - 1;
       else
           //Otherwise set the beginning to mid plus 1
           Beg = Mid + 1;
       }
       //If flag value is 0 Item not available
       if(Flag == 0)
           System.out.println(" Item " + st + " not available ");
       return count;
   }
   //Displays the list
   static void disp(String myList[])
   {
       for(int x = 0; x < 10; x++)
           System.out.print(myList[x] + " ");
   }
   //Sorts the list
   static void sort(String st[])
   {
       for(int x = 0; x < 10; x++)
       {
           for(int y = x; y < 10 - 1; y++)
           {
               if(st[y].compareTo(st[y+1]) > 0)
               {
                   //Swapping process
                   String t = st[y];
                   st[y] = st[y+1];
                   st[y+1] = t;
               }
           }
       }
   }
   //linearSearch method to search a string and display number of iteration required
   static int linearSearch(String myList[], String s)
   {
       int count = 0;
       for(String st : myList)
       {
           //Increase the counter for comparision
           count++;
           if(st.equals(s))
           {
               break;
           }
       }
       return count;
   }
   public String toString(String ss[])
   {
       String msg = "";
       for(String st : ss)
           msg += st;  
       return msg;
   }
}//End of class

Output:

List Not Sorted:
Dil Barsat Asique City Chalbaj Danger Nastik Love Noise Rang
Linear search
Number of Iteration required for first item: 3
Number of Iteration required for for last item: 10
After Sorted:

Barsat Asique Chalbaj City Danger Dil Love Nastik Noise Rang
Binary search

Item Asique Found in 1 Position
Number of Iteration required for first item: 2

Item Rang Found in 9 Position
Number of Iteration required for for last item: 4

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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