Array Binary Search
Intermediate Level

Implement the findRotationCount method that returns how many times a sorted array has been rotated.

The input contains a rotated sorted array nums and its length size. Your task is to return how many times the sorted array has been rotated.

The rotation count is the index of the smallest value. For example, in [4,5,6,1,2,3], the smallest value 1 is at index 3, so the rotation count is 3.

Example 1
Input:
nums (int[]) = [4,5,6,1,2,3]
size (int) = 6
Return:
(int) 3
Example 2
Input:
nums (int[]) = [1,2,3]
size (int) = 3
Return:
(int) 0
Example 3
Input:
nums (int[]) = [3,1,2]
size (int) = 3
Return:
(int) 1

Finding the rotation count is the same as finding the index of the minimum value.

Use binary search. If the middle value is greater than the rightmost value, the minimum value must be on the right side. Otherwise, the minimum value is at the middle position or on the left side.

When the search ends, the left pointer points to the smallest value, which is the rotation count.

Pseudocode:

function findRotationCount(nums, size):
    if size == 0:
        return 0
    left = 0
    right = size - 1
    while left < right:
        mid = (left + right) / 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return left
Run your code to see the result.