Find Minimum in Rotated Sorted Array II

LeetCode Q 154 - Find Minimum in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element. The array may contain duplicates.

Solution

Similar to Q81, in the worst case, the time complexity becomes O(n).
So, we don’t need to use binary search.

Code:

public int findMin(int[] nums) {
	int min = nums[0];
	for (int i = 1; i < nums.length; i++) {
		if (nums[i] < min) min = nums[i];
	}
	return min;
}

Code: Use fake binary sesarch

public int findMin(int[] nums) {
	int left = 0, right = nums.length - 1;
	while (left < right) {
		int mid = (left + right) / 2;
		if (nums[mid] > nums[nums.length - 1]) left = mid + 1;
		else if (nums[mid] == nums[nums.length - 1]) right--;
		//When num[mid] == num[hi], we couldn't sure the position of minimum in mid's left or right, 
		//so just let upper bound reduce one.
		else right = mid;
	}
	return nums[left];
}