Consider an array A consisting of distinct values that has first been sorted and then been rotated
Question:
Consider an array A consisting of distinct values that has first been sorted and then been rotated by some unknown distance d ≥ 0. For instance, the array A = [11; 14; 17; 2; 4; 5; 7; 9] has been obtained from [2; 4; 5; 7; 9; 11; 14; 17] by a rotation by d = 3 positions. You can also think of a rotation as a right shift by d positions, after which all the elements pushed out of the array are again fed into the left hand side. The algorithm to be developed in this exercise receives as input a rotated sorted array, where the rotation distance is unknown. The algorithm returns the index of the minimum.
Your goal is to develop an efficient algorithm.
Proceed as follows:
1. Describe your idea for the algorithm and provide arguments why it solves the problem.
2. Try to develop tests for the algorithm, covering both special and general cases. (There is already one test for the example above.)
3. Write pseudocode for your solution.
4. Implement your solution in Java.
Expert Answer:
