Question

Write a Java program with comments that randomly generates an array of 500,000 integers between 0 and 499,999, and then prompts the user for a search key value. Estimate the execution time of invoking the linearSearch method in Listing A below. Sort the array and estimate the execution time of invoking the binarySearch method in Listing B below. You can use the following code template to obtain the execution time:

long startTime = System.currentTimeMillis();

perform the task;

long endTime = System.currentTimeMillis();

long executionTime = endTime - startTime;

A. Linear Search

public static int linearSearch(int[] list, int key) {

for (int i = 0; i < list.length; i++) {

if (key == list[i]) return i;

}

return -1;

}

B. Binary Search

public static int binarySearch(int[] list, int key) {

int low = 0;

int high = list.length - 1;

while (high >= low) {

int mid = (low + high) / 2;

if (key < list[mid])

high = mid - 1;

else if (key == list[mid])

return mid;

else

low = mid + 1;

}

return –low - 1; // Now high < low, key not found

}

Answer 1

For the above program, we need to have the following things into consideration.

1. We need to first use the random class function in order to find the integers for the array.
2. Then we can search for the middle element for example and then calculate the time accordingly.

Following is the code for the same.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class ComparisonOfSearches {
   public static void main(String args[]) {
       Random rand = new Random();
       int list[] = new int[500000];
       for(int i = 0 ;i<500000; i++) {
           list[i] = rand.nextInt()%500000;
       }
       int middleElement = list[250000];
       long start_linear = System.currentTimeMillis();
       int found = linearSearch(list, middleElement);
       long end_linear = System.currentTimeMillis();
       System.out.println("Time Taken by linear search: " + (end_linear - start_linear));
       Arrays.sort(list);
       long start_binary = System.currentTimeMillis();
       found = binarySearch(list, middleElement);
       long end_binary = System.currentTimeMillis();
       System.out.println("Time Taken by binary search: " + (end_binary - start_binary));
   }
   public static int linearSearch(int[] list, int key) {

       for (int i = 0; i < list.length; i++) {

       if (key == list[i]) return i;

       }

       return -1;

   }
   public static int binarySearch(int[] list, int key) {

       int low = 0;

       int high = list.length - 1;

       while (high >= low) {

       int mid = (low + high) / 2;

       if (key < list[mid])

       high = mid - 1;

       else if (key == list[mid])

       return mid;

       else

       low = mid + 1;

       }

       return -1; // Now high < low, key not found

   }
  
}

Following is the output of the above program.

That was a nice question to answer
Friend, If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Please like if you think effort deserves like.
Thanks