Step 1: Modify linearSearch and binarySearch methods to return an array containing key index and number steps taken in s

[answerhappygod]

Step 1 Modify Linearsearch And Binarysearch Methods To Return An Array Containing Key Index And Number Steps Taken In S 1 (51.88 KiB) Viewed 75 times

Step 1 Modify Linearsearch And Binarysearch Methods To Return An Array Containing Key Index And Number Steps Taken In S 2 (37.87 KiB) Viewed 75 times

Step 1 Modify Linearsearch And Binarysearch Methods To Return An Array Containing Key Index And Number Steps Taken In S 3 (49.84 KiB) Viewed 75 times

Step 1 Modify Linearsearch And Binarysearch Methods To Return An Array Containing Key Index And Number Steps Taken In S 4 (61.9 KiB) Viewed 75 times

Step 1 Modify Linearsearch And Binarysearch Methods To Return An Array Containing Key Index And Number Steps Taken In S 5 (47.74 KiB) Viewed 75 times

Step 1: Modify linearSearch and binarySearch methods to return an array containing key index and number steps taken in search As we want to experimentally compare the linear search and binary search strategies, we will need to modify the methods to keep track of the numbers of steps taken in the search. It would be nice if we could return the index at which the key was found (-1 if not found) and the number of steps it took to find the key. This can be achieved by returning an integer array that contains the index and the number of steps. int[] result = new int[21: Index of search keyif found, -1 if not found Number of steps taken in search So, we will need to change the return type of the search methods to int[] and create an integer array called results to store the key index and number of steps taken. We will also need a steps variable (initialised to zero) to keep track of the number of search steps. // Linear search method that returns an integer array as follows: // resulte: this will hold the index of k it found or -1 rant this will hold the number of steps taken in search public static int Il linear Search intl array, int k){ int results = new int[2: int steps = 0; // Binary search method that returns an Integer array as follows: // result(o): this will hold the index of k if found or -1 1 result[1]: this will hold the number of steps taken in search public static int Il binary Seargh(intlarray, int k) int!results new int 123 int steps = 0; Step 2: Modify the search method code to keep count of the search steps taken We need to increment (by 1) the steps variable on each iteration of the search loop Linear Search Loop Il continue to search until end or value found for (int i = 0; i < array.length; i++) { 77 count the steps steps++; Binary Search Loop // Loop until low > High while(low high) 77 count the steps steps++;
Step 3: Modify the search method code to return the key index (-1 if not found) and the number of steps taken Looking at each search method (Linear and Binary), there are two cases where the return keyword is used. Case 1: Inside the search loop -> search key has been found Case 2: After the search loop -> search key has not been found We need to modify the return statement in each case to return the results array instead of a single result variable Returning the results for Linear Search Case 1 Linear Search FOUND: return i and steps We found 1/ Load up the results of the search results[0] = 1; results[1= steps: return results: Case 2 Linear Search NOT FOUND: return-1 and steps // We have not found 1 Load up the results of the search results to -1; results[1] = steps: return results: Returning the results for Binary Search Case 1 Binary Search FOUND: return mid and steps We found 1/ Load up the results of the search resultstol = sid: results 1 - steps: return results; Case 2 Binary Search NOT FOUND: return-1 and steps Heave not found // Load up the results of the search resultsto-1: results - steps: return results: For example, we can make a call to the linear Search method like this: 1/ Paraneter 1: data is the 250 sorted values in the data array 1/ Parameter 2: K is a randomly generated search key between 3-880 // Return value: int where first value is Index or -1, and second value is steps intl linearResult linear Search(data, k); // LinearResult[] = index of search key or -1 1 Linear Result[1] = steps taken in the search
Step 4: Writing the experiment code The idea behind this experiment is to compare the average numbers of steps in Linear Search with the average number of steps taken in Binary Search. To do this we will use a data array that contains 250 random integers between 0-800 that are sorted in ascending order. To test each search method, we will generate a random search key between 0-800 and then use each search method to determine the number of steps taken in the search. As we will use a random search key. we need consider the following possibilities: 1. Search key found at first position - best case 2. Search key found somewhere in the middle of the array average case 3. Search key at last position or not present -worst case Therefore, we cannot use a single trial for each search method. We must take the average number of steps taken over many search trials with different search keys. For our experiments we will use 1000 trials with 1000 random search keys. int nunTrials = 1900 // Number of trials for each search int linearSteps 1/ Sun up the number of linear Search steps int binarySteps = 0; 1 Sun up the number of binary Search steps We can use a loop to test each search method with a random search key and keep a running sum of the steps taken to calculate the average number of steps taken over 1000 trials. The following code can be used as a template for the experiment loop. // Run the search trial 1000 times for (int i = 0; i < nunTrials 1/ Generate a random search key between 2-300 1/ Call the search method with the random search 1/ Keep a running sum of the steps taken > 1 Calculate the average steps taken The overall output of the finished program should look something like this... Array size is n=250 EXPERIMENT 1 Linear Search Trials Average #steps to find random k in 1988 trials is 228.00 EXPERIMENT 2 Binary Search Trials Average Esteps to find randonk in 2008 triats is 7.00 Add comments to your code to answer the following questions: QUESTION 1: is the performance of linear search approximately O(n)? QUESTION 2: is the performance of binary search approximately O[log2[n])? NOTE: you can use the online log calculator at https://www.omnicalculator.com/math/log-2
public class SearchExperiments static final int[] data = {0,1,2,6,8,9,15,17,18,25,26,29,30,32,33,36,38,43,44,45,55,56,59, 60, 61, 62, 63, 64, 65, 77, 84, 85, 86, 90,94,96, 100, 103, 104, 108, 109, 112, 114, 122, 123, 124, 128, 130, 131, 141, 147, 154, 155, 164, 166, 169, 170, 174, 175, 178, 180, 185,187, 190, 194, 196,206, 209, 210, 211, 214, 218,222,225, 228, 235, 240, 241, 244, 245, 248, 250, 252, 253, 255, 258, 259, 260, 267, 268, 270, 276, 278, 279, 280, 284, 286, 289, 292,302,326,332,336,338, 348,359,365,367,368,371,373, 376,377,378, 379, 382, 386,387,392,405,407,409,414,415,419,426,428,431,433,434,438, 439,443,444,447,448,455,457,459,460,468,469,477,479,480,481,486,487, 489, 492, 495,498,499, 501, 505,506,510,511,513,521,531,532,533,537,538, 539,543, 545, 547,548,554,559,561,563,564,566,577,580,581,589,592,594, 595,597,599,620, 604,605, 609, 614,617,618,621,623,624,625, 627,632,634, 636, 641, 642,644,645,646,649, 650, 652,654, 659,661,663,671,672,674,677, 680,682,683,688,689,692,694,696,700,703,705,786,707,708,714,716,718, 725,730, 732,734,737,740, 741,742,752,754,755, 757,760,762,763,764,765}; // MODIFY - to return an int[] public static int linearSearch(int[] array, int k){ // Continue to search until end or value found for(int i = 0; i < array.length; i++){ // Check current item if (array = k){ 17 We found return i; ) ) // We have not found k return -1; // MODIFY - to return an int[] public static int binarySearch(int[] array, int k){ // Set the initial high and low int low = 1; int high = array.length - 1; // Loop until low > high while(low <= high)
// Calculate the midway index int mid = (low + high) / 2; //System.out.println("Mid = + mid); if (k > array[mid)) // k in the upper part low = mid + 1; else if (k < array[mid]) // k in the lower part high = mid - 1; else if (k == array[mid]){ // We found k return mid; } } // We have not found k return -1; } public static void main(String[] args) { int numTrials = 1000; // Number of trials for each search int linearSteps = 0; // Sum up the number of linearSearch steps int binarySteps = 0; // Sum up the number of binarySearch steps System.out.printf("Array size is n=%d\n\n", data. length); System.out.println("EXPERIMENT 1"); System.out.println("Linear Search Trials"); System.out.println("======== =========="); // Loop for experiment 1 here System.out.println("EXPERIMENT 2"); System.out.println("Binary Search Trials"); System.out.println("====== ========"); // Loop for experiment 2 here }