I would prefer java Implement linearSearch(a,key) Part A. In this part we will c
ID: 3726522 • Letter: I
Question
I would prefer java
Implement linearSearch(a,key)
Part A. In this part we will calculate the average-case running time of each function.
1. Request the user to enter a positive integer, and call it n. (n = 10^5 )
2. Generate n random integers between -1000 to 1000 and save them in array a.
3. Sort a (you can use any sorting algorithm you want. If you are using MATLAB, you can call the sort function to sort your numbers)
4. Pick a random number in a and save it in variable called key.
5. Call each function separately to search for the key in the given array.
6. To calculate the average-running time, you need to have a timer to save the total runtime when repeating step 4 and 5 for 500 times. (tic toc in MATLAB)
(Note1: Do not forget to divide the runtime by the number of the times you run step 4-5)
(Note2: Remember to choose a different random number each time you go back to step 4.)
Explanation / Answer
import java.util.Random;
import java.util.Scanner;
public class LinearSearchTime {
// This function returns index of element x in arr[]
static int linearSearch(int arr[], int x)
{
for (int i = 0; i < arr.length; 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;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n value: ");
int n = sc.nextInt();
int[] arr = new int[n];
Random rn = new Random();
int r = 1000 - (-1000) + 1;
for(int j=0; j<n; j++) {
int randomNum = rn.nextInt() % r + (-1000); // -1000 to 1000
arr[j] = randomNum;
}
//picking a random number on range 0 to n-1
long totalTime = 0;
long start, end;
for(int i=1; i<=500; i++) {
int key = arr[rn.nextInt(n)];
start = System.currentTimeMillis();
linearSearch(arr, key);
end = System.currentTimeMillis();
totalTime = totalTime + (end - start);
}
System.out.println("Average time: "+(totalTime/500.0));
}
}
/*
Sample run:
Enter n value: 1000
Average time: 0.012
*/