Find rotation count in rotated sorted array

Problem

Question : Find the minimum element in the rotated sorted array.

Example

Example 1:

Input: nums = [5, 7, 9, 1, 3]
Output: 3
Explanation: The original array was [1, 3, 5, 7, 9] rotated 3 times.

Solution

This can be solved in linear time and logarithmic time. If we notice the above array, we see the array has been rotated 2 times, which is also the index of smallest element in the array. So, we need to find the point of inflection where we find a point such that a[i]>a[i+1].

So, finding the minimum element in the rotated sorted array has been implemented here - Find Minimum in Rotated Sorted Array. The implementation is exactly same, except that in this case we return the index of the minimum element instead of the minimum element itself.

Method 1 - Iterative

class Solution {
	/*
	To understand the boundaries, use the following 3 examples:
	[2,1], [2,3,1], [3,1,2]
	*/

	public int findMin(int[] nums) {
		if (nums == null || nums.length == 0) {
			return -1;
		}

		int left = 0;
		int right = nums.length - 1;

		while (left <= right) {
			if (nums[left] <= nums[right]) {
				return left;
			}

			int mid = (left + right) / 2;

			if (nums[mid] >= nums[left]) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}

		return -1;
	}
}