154 - Find Minimum in Rotated Sorted Array II
Written on October 21, 2015
Tweet
Suppose a sorted array 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.
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (nums[mid] < nums[hi]) {
hi = mid;
} else if (nums[mid] > nums[hi]) {
lo = mid + 1;
} else {
hi --;
}
}
return nums[lo];
}
}
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] < nums[hi]:
hi = mid
elif nums[mid] > nums[hi]:
lo = mid + 1
else:
hi -= 1
return nums[lo]