Searching

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

1. Generate the array of the given data type and size. Populate with random numbers in sorted order (duh!)
2. Implement the usual suspects:
   1. Linear search
   2. Binary search
   3. Exponential search
3. Implement different optimizations for each of these
4. 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?