Find Minimum in Rotated Sorted Array II
Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
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.
标签: Array Binary Search
class Solution: # @param num, a list of integer # @return an integer def findMin(self, num): n = len(num) low = 0 high = n-1 while low < high: if num[low] < num[high]: return num[low] mid = int((low + high)/2) if num[mid] > num[high]: low = mid+1 elif num[mid] == num[high]: low += 1 else: high = mid return num[low]