Labwork 5

SEARCHING ALGORITHM

* setup

- In the main(), create an array arr of size s1= 1000000 and initialize it with sorted values. >

1 - Implement int linear_search(int[] arr, int target) function in Java

2 - Implement int binary_search_iterative(int[] arr, int target) function in Java as an iterative function (no recursive calls)

3- Implement int binary_search_recursive(int[] arr, int target) function in Java as an recursive function (the function may call itself)

4- Call the linear_search() and binary_search() and verify that they are working as expected.

5- Debug the code to understand the implementation.

>

6 - Call linear_search 100 times to find a random target for input of size s1 and print out the average time it took to run the code.

7 - Call linear_search 100 times to find a random target for input of size s2 where s2 = 100 * s1

What is growth rate of time 6 & 7 steps . . . . . . .

8 - Call binary_search 100 times to find a random target for input of size s1 and print out the average time it took to run the code.

9 - Call binary_search 100 times to find a random target for input of size s2 where s2 = 100 * s1 . . . . . .

What is the growth rate of time for 8 & 9?

Reference Code

Binary Search - Recursive:

Please send me the screenshot of final result too..

Thank you

int binarySearch(int arr[], int i, int r, int x) { if (r >= 1) { int mid = 1 + (r - 1) / 2; // If the element is present at the // middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not present // in array return -1; } Reference code Linear search: public static int search(int arr[], int x) { int n = arr.length; for (int i = 0; i = 1) { int mid = 1 + (r - 1) / 2; // If the element is present at the // middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not present // in array return -1; } Reference code Linear search: public static int search(int arr[], int x) { int n = arr.length; for (int i = 0; i