441. Number of Times Array is Rotated

A sorted array of distinct integers was rotated k times (0 ≤ k < n). Given the rotated array, return k — the number of times it was rotated. This equals the index of the minimum element. Solve in O(log n).

Input: A rotated sorted array of distinct integers.

Output: Number of rotations (index of the minimum element).

Examples

Input: [4,5,6,7,0,1,2]
Output: 4
Explanation: Minimum 0 is at index 4; array was rotated 4 times.

Input: [1,2,3,4,5]
Output: 0
Explanation: Not rotated; minimum is at index 0.

Input: [3,4,5,1,2]
Output: 3
Explanation: Minimum 1 is at index 3.

Constraints

• 1 <= nums.length <= 5000
• All distinct
• -5000 <= nums[i] <= 5000

Asked by