Question

Implement a method that meets the following requirements:

(a) Takes as parameter 1) an int array A 2) an int number x to search for

(b) determines whether x exists in A, and prints a message indicating the result

(c) has the best worst case Big Oh complexity you can manage, using only your own thinking and the materials (the worst case growth rate for the number of items searched should be as low as possible, given that A contains n items.)

(d) In comments above the method, explain what its algorithmic complexity is and why (constant, logarithmic, linear, quadratic...)

Answer 1

CODE IN JAVA:

Search.java file:

public class Search {
   //the time complexity of this method is linear
   public static void linearSearch(int[] arr, int num) {
       boolean flag = true;
       int ind = -1;
       for(int i=0;i<arr.length;i++) {
           if(arr[i]==num) {
               System.out.println("Your number is found at index "+i);
               flag = false;
               break;
           }
       }
       if(flag)
           System.out.println("You number is not found");
   }
   public static void main(String[] args) {
       // TODO Auto-generated method stub
       int arr[] = {9,1,5,3,8,10,34,65,3};
       int num = 10;
       System.out.println("The array is:");
       for(int i=0;i<arr.length;i++)
           System.out.print(arr[i]+" ");
       System.out.println("\nThe number to be searched is:"+num);
       linearSearch(arr,num);

   }

}
OUTPUT: