Question

Questions 1a and 1b are about the linear search algorithm that was discussed in the lectures.

1a. Write a Java method called stringyLinear that performs linear search on an array of String’s, so it is defined as follows. Your code appears in place of the three dots ‘‘⋅⋅⋅’’. Do not write a class, only a method.

If a String equal to key appears in keys, then stringyLinear must return an index in keys where it appears. If no String equal to key appears in keys, then stringyLinear must return −1. Assume that no element of keys is null, and that key is not null.

1b. Suppose that a linear search method is given an array whose length is n, where n ≥ 1. Show that the algorithm performs O(n) key comparisons in the average case. For full credit, you must do this by finding constants c and n₀.

Answer 1

Ia.
    public int StringyLinear()throws IOException
{
   BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

   System.out.println("Enter the size of the array: ");
   int n= Integer.parseInt(br.readLine());

   String A[]= new int [n];

   System.out.println("Enter the elements of the array: ");
   for(int i=0; i<n; i++)
   {
       System.out.println("Enter the "+i+"th element of the array: ");
       A[i]= br.readline();
   }
   int pos=-1;
   System.out.println("Enter the key to be searched: ");
   String key= br.readLine();
   boolean found = false;

   for(int i=0; i<n; i++)
   {
       if(key.equalsIgnoreCase(A[i])
       {   found=true;
           pos=i; break; }
   }      

           if(found)
                  return pos;
            else
              return -1;
   }

1b. In average case analysis, we take all possible inputs that may or may not be uniformly distributed and calculate the time taken.Sum all the calculated values and divide the sum by total number of inputs.

f(n)<=c.g(n), n>=n_0,

c=1, n>=0, n₀=0.