Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
[0,1,2,4,5,6,7] might become
Find the minimum element.
You may assume no duplicate exists in the array.
Input: [3,4,5,1,2] Output: 1
Input: [4,5,6,7,0,1,2] Output: 0
Hint 1Array was originally in ascending order. Now that the array is rotated, there would be a point in the array where there is a small deflection from the increasing sequence. eg. The array would be something like [4, 5, 6, 7, 0, 1, 2].
Hint 2You can divide the search space into two and see which direction to go. Can you think of an algorithm which has O(logN) search complexity?
- All the elements to the left of inflection point > first element of the array.
- All the elements to the right of inflection point < first element of the array.