Need help with a linear search program in three different ways: single-threaded, multi-threaded, and parallel. Each approach will be a separate class.

For the single-threaded search, you will perform a basic linear search. When you find the value, you should return the index (-1 if not found) and then print out the amount of time that elapsed.

For the multi-threaded search, you need to split the array into smaller sub-arrays. Instead of creating new arrays of smaller size, you should pass the start and end indexes into your thread's constructor and only search the specified subarray in the thread. Start off with splitting the array into 4 subarrays, and then instantiate a new thread for each subarray where you linear search. If you find the value, return the index and print out the amount of time that elapsed. Note that your other threads will probably still be running, but we don't care about the time for all the threads to complete - we only care about the time it takes to find the random number. If you didn't find the number, then print out the total time for all the threads to complete.

For the parallel search, you will split the array into smaller subarrays similarly to what you did in the multi-threaded approach. Each parallel thread will also need the start index, end index, target number, and start time. Start off again with 4 threads. When you find the value, return the index and print out the amount of time that elapsed. Again, print out the time as soon as you find the number - we don't care if all the threads are finished. We only care about all the threads finishing if the number is not in the array.

Now let's create the help class. In the helper class, instantiate an array with 100,000,000 unique integers (One way to come up with unique integers is to make the values be equivalent to the indexes initially, then shuffle the array). Generate a random integer between 0 and 100,000,000-1, which will be your first target number. Generate another integer that is NOT in the array to be your second target number. Use the three classes above to find your target numbers and check if they have all returned the same index by printing them out. Make sure you are using the same array, so that we can compare the run times. Do not modify the array since we want to compare the running times on the same array.