Input
Array size, data type, search algorithm, key. The key can specified as an index or as a non-existent value
Output
index, if key is in the array, -1 otherwise. Running time
Program
- Generate the array of the given data type and size. Populate with random numbers in sorted order (duh!)
- Implement the usual suspects:
- Linear search
- Binary search
- Exponential search
- Implement different optimizations for each of these
- Test that the search is correct
Run
your implementation. There can be many variations in here, based on where the key is. Compare the performance of different searches for keys at the beginning, middle and end of the array. What do you think is the best-, average- and worst-case situation for each search? Do the performance results match your intuition? There are different ways of analyzing the performance, such as time v. array size for different key locations, or time v. key location for different array sizes, or …. What do you choose?
Report
your findings! Can you correlate these to the theoretical analysis and the architecture of your platform?