Write a Java program to compare the execution time of linear search and the exec

Question

Write a Java program to compare the execution time of linear search and the execution time of binary search. Within your program you define the linear iterative search method,

the linear recursive search method, the binary iterative search method, and the binary recursive method discussed in our lecture. Your program will ask the user to input the size (at least 5000) of one array that will store integers with increasing order. Before invoking the above four methods, your program also will ask the user to input a target integer and an integer for the number of execution times for each method. Your program will display execution time of each method above. Notice that

long currTime = System.currentTimeMillis( )

will assign the current time in term of milliseconds since midnight, January 1, 1970 to

the variable currTime of type of long.

Explanation / Answer

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class SearchTest {

   // This function returns index of element x in arr[]
static int iterativeLinearSearch(int arr[], int n, int x)
{
for (int i = 0; i < n; i++)
{
// Return the index of the element if the element
// is found
if (arr[i] == x)
return i;
}
  
// return -1 if the element is not found
return -1;
}
  
// This function returns index of element x in arr[]
static int recursiveLinearSearch(int arr[], int l, int r, int x)
{
   if (r < l)
   return -1;
   if (arr[l] == x)
   return l;
   return recursiveLinearSearch(arr, l+1, r, x);
}
  
// Returns index of x if it is present in arr[l..r], else
// return -1
static int recursiveBinarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;

// If the element is present at the middle itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then it can only
// be present in left subarray
if (arr[mid] > x)
return recursiveBinarySearch(arr, l, mid-1, x);

// Else the element can only be present in right
// subarray
return recursiveBinarySearch(arr, mid+1, r, x);
}

// We reach here when element is not present in array
return -1;
}
  
   // A iterative binary search function. It returns location of x in
   // given array arr[l..r] if present, otherwise -1
   static int iterativeBinarySearch(int arr[], int l, int r, int x)
   {
   while (l <= r)
   {
   int m = l + (r-l)/2;
  
   // Check if x is present at mid
   if (arr[m] == x)
   return m;
  
   // If x greater, ignore left half
   if (arr[m] < x)
   l = m + 1;
  
   // If x is smaller, ignore right half
   else
   r = m - 1;
   }
  
   // if we reach here, then element was not present
   return -1;
   }
  
   public static Random rn = new Random();
     
   public static void fillArray(int []arr, int n)
   {
       for(int i = 0; i < n; i++)
       {
           arr[i] = rn.nextInt()%10000;
       }
   }
     
   public static void main(String[] args)
   {
       Scanner sc = new Scanner(System.in);
         
       int n;
       while(true)
       {
           System.out.print("Enter number of element in array (atleast 5000): ");
           n = sc.nextInt();
           if (n < 5000)
           {
               System.out.println("Number is below 5000 try again.");
           }
           else
           {
               break;
           }
       }
       int[] arr = new int[n];
         
       fillArray(arr, n);
       Arrays.sort(arr);
       System.out.print("Enter a number to find: ");
       int num;
       num = sc.nextInt();
         
       System.out.print("Enter number of execution: ");
       int execN = sc.nextInt();
       long time;
       double avgTimeMs;
         
       time = 0;
       for (int i = 0; i < execN; i++)
       {
           long startTime = System.currentTimeMillis( );
           iterativeLinearSearch(arr, n, num);
           time += System.currentTimeMillis( ) - startTime;
       }
       avgTimeMs = (double)(time)/execN;
       System.out.println("Average time taken by iterative linear search: " + avgTimeMs);
         
       time = 0;
       for (int i = 0; i < execN; i++)
       {
           long startTime = System.currentTimeMillis( );
           recursiveLinearSearch(arr, 0, n-1, num);
           time += System.currentTimeMillis( ) - startTime;
       }
       avgTimeMs = (double)(time)/execN;
       System.out.println("Average time taken by recursive linear search: " + avgTimeMs);
         
       time = 0;
         
       for (int i = 0; i < execN; i++)
       {
           long startTime = System.currentTimeMillis( );
           iterativeBinarySearch(arr, 0, n-1, num);
           time += System.currentTimeMillis( ) - startTime;
       }
       avgTimeMs = (double)(time)/execN;
       System.out.println("Average time taken by iterative binary search: " + avgTimeMs);
         
       time = 0;
       for (int i = 0; i < execN; i++)
       {
           long startTime = System.currentTimeMillis( );
           recursiveBinarySearch(arr, 0, n-19, num);
           time += System.currentTimeMillis( ) - startTime;
       }
       avgTimeMs = (double)(time)/execN;
       System.out.println("Average time taken by recursive binary search: " + avgTimeMs);
   }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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