Implement a method that will search a given array using the linear search algorithm.

Implement a method that will search a given array using a recursive binary search algorithm.

Write a driver program to test the methods implemented in questions $1-2.$ Note that you have to sort the input array before using the binary search algorithm, you can use any sort method available $($e$.$g$.,$ sort method in the Java Collection Framework$).$

You need to create multiple datasets to test the speed of your algorithms. Test the program for array sizes $N=16,32,64,128,256,512,1024,2048,$dotsdots,$2^{20}.$ Initialize the array with random numbers between the ranges $1$ through $N($Please note that we will be using these datasets for both linear search and binary search. Remember to sort the array before using binary search. These datasets will be our dataset that we will be searching our keys inside those datasets

Use a text file with $1,000$ random numbers in the range $1$ through $1000$ as the search keys. You need to search all those $1000$ numbers inside every dataset.

$$

Compare the execution time for linear search and binary search. Include the time taken for sorting with the binary search time $($you have to sort only once for each array size$).$ Use a table or plot to summarize the results and document your observations and explanations in the report.