Question
I would prefer java
Implement linearSearch(a,key) and binarySearch(a,key) functions.
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
public class Search { private int n; public void getN(int a) { this.n = a; } int[] a; public int[] getArray(int n) { this.a = new int[n]; return a; } public static int setRandom() { int random = (int) (Math.random() * 1000 + (-1000)); return random;} public static int getRandomNumberFromArray(int[] array) { int rndArray = new Random().nextInt(array.length); return array[rndArray]; } public int linearSearch(int arr[], int x) { Instant startTime = Instant.now(); for (int i = 0; i =l) { int mid = l + (r - l)/2; // If the element is present at the // middle itself if (arr[mid] == x) {DateTime endTime = DateTime.now(); System.out.println("Start Time of Binary Search" + startTime); System.out.println("End Time of Binary Search" + endTime); Period p = new Period(startTime, endTime, PeriodType.millis()); System.out.println("Total duration for Binary Search = " + p.getValue(0)); return mid;} // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch1(arr, l, mid-1, x, startTime); // Else the element can only be present // in right subarray return binarySearch1(arr, mid+1, r, x, startTime); } // We reach here when element is not present // in array return -1; } int binarySearch1(int arr[], int l, int r, int x, DateTime startTime) { if (r>=l) { int mid = l + (r - l)/2; // If the element is present at the // middle itself if (arr[mid] == x) { DateTime endTime = DateTime.now(); System.out.println("Start Time of Binary Search" + startTime); System.out.println("End Time of Binary Search" + endTime); Period p = new Period(startTime, endTime, PeriodType.millis()); System.out.println("Total duration for Binary Search = " + p.getValue(0)); return mid; } // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch1(arr, l, mid-1, x, startTime); // Else the element can only be present // in right subarray return binarySearch1(arr, mid+1, r, x, startTime); } // We reach here when element is not present // in array return -1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] Array; Search search = new Search(); search.getN(n); Array = search.getArray(n); System.out.println(search.a.length); for(int i = 0; i