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 1 - No duplicates allowed. 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;
	}
}