Write a program that randomly generates an array of 100,000 integers and a key. Estimate the execution time of invoking the linearSearch method in Listing 7.6. Sort the array and estimate the execution time of invoking the binarySearch method in Listing 7.7. 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;

LISTING 7.6 LinearSearch.java 1 public class LinearSearch { /** The method for finding a key in the 1ist */. 3 public static int linearSearch(int[] list, int key) { 4 2 for (int i = 0; i < list.length; i++) { 5 if (key == list[i]) [0] [1] [2] ... list return i; } return -1; } 7 8 key Compare key with list[i] for i = 0, 1, ... 10 }