Task Requirements In this lab, you will write a Java program to search for an integer in an array using binary search algorithm and linear search algorithm - both implemented iteratively and recursively. You will use two built-in methods namely nanoTime() and currentTimeMillis() to compute the time taken by each of the search algorithms. A hint is given below - see (g). Classes: BinaryLinearSearch class Instance variables Private data members and Scanner object. You may choose to include here all instance variables shared by both recursive and non-recursive methods. These may include shared array index and search key variables. Methods iterativeBinarySearch (uses iterative/looping construct) Receives an array of integers and the search key number to search. If the number is present in the array the method returns its index location and prints the message: number ___ found at index ___: Iterative Binary Search on the screen. If the number is not found in the array the method returns a sentinel value of -1 and prints the message number _ was not found. recursiveBinarySearch (uses recursion) A method that receives an array of randomly generated integers, the first index and last index of the array, and the number to search. The method then recursively searches for the number entered by the user on the keyboard. Returns the index position if the number is present in the array and prints the message number ___ found at index ___: Recursive Binary Search on the screen. Returns a sentinel value of -1 if the number is not found and prints the message number __ was not found. ( the __ represents the search key). generateRandomInts Uses the more SecureRandom class to generate random integers between 10 and 100. Returns an array of random numbers: randomArr, that is, an array that will be populated with 32 randomly generated integer values mainly in the range of 10 to 100 boundary values excluded i.e. 10

boundary values excluded i.e. 10Note: Both binary search and linear search methods will use same sorted array even though linear search algorithm does not always array to be sorted. Also make generateRandomInts display the unsorted random array with menu option 1. This means that when the user selects menu option 1, we should see two versions of the randomly generated array: the unsorted array and the sorted array.

remainingElements. This method displays elements remaining each time a half of the array is dropped.

iterativeLinearSearch (uses iterative looping construct). Receives an array of integers and the search key number to search. If the number is present in the array the method returns its index location and prints the message: number___ found at index ___: Iterative Linear Search on the screen. If the number is not found in the array the method returns a sentinel value of -1 and prints the message number _ was not found.

recursiveLinearSearch (uses recursion). A method that receives the array of randomly generated integers (from generateRandomInts - see (c) above), the array size, and the element to search. The method then performs recursive linear search for the number entered by the user on the keyboard. Returns the index position if the number is present in the array and prints the message number ___ found at index ___: Recursive Linear Search on the screen. Returns a sentinel value of -1 if the number is not found and prints the message number __ was not found. ( the __ represents the search key).

System.nanotime() and System.currentTimeMillis() methods. Use these two methods of the System class to determine how long the iterative and recursive binary and linear search operations in steps (a), (b), (e) and (f) and calculates the processing time taken in nanoseconds and milliseconds. Time taken by each operation should be displayed on the screen. Hint: wrap each method in steps (a, (b), (e) and (f) with the timing methods.

You may create one additional method in case you need one - not a graded requirement.