Linear Search

Write a class LinearSearch that takes an int Array as a parameter when the LinearSearch object is constructed. The array of values may be sorted or not. The class should include an int method find(int n) that looks for a value n in the array, and returns the first location (index) of that value in the array.

If the value n isn't found in the array, the method should return a value of -1 to indicate that the search failed.

Write a LinearSearchDemo.java that creates an array of values and a LinearSearch object, and the demonstrates the use of the find() method.

Extension

1. If there are num elements in an array, about how many numbers (on average) will the linear search algorithm need to check before finding the position of a value n?
2. Does the average number of values that we need to look through decrease, increase, or stay the same as the number of elements we have to look through increases?
3. Based on this analysis, what is the Big-O performance of the linear search algorithm?
   • O(1)?
   • O(n)?
   • O(log n)?
   • O(n log n)?
   • O(n2)?