As explained in the Solution tag, the key to solving this problem is to use invariants. We set two pointers: l for the left and r for the right. One key invariant is nums[l] > nums[r]. If this invariant does not hold, then we know the array has not been rotated and the minimum is justnums[l]. Otherwise, we reduce the search range by a half each time via comparisons betweennums[l], nums[r] and nums[(l + r) / 2], denoted as nums[mid]:
- If
nums[mid] > nums[r], thenmidis in the first larger half andris in the second smaller half. So the minimum will be right tomid, updatel = mid + 1; - If
nums[mid] <= nums[r], then the minimum is at leastnums[mid]and elements right tomidcannot be the minimum. So updater = mid(note that it is notmid - 1sincemidmay also be the index of the minimum).
When l == r or the invariant does not hold, we have found the answer, which is just nums[l].
Putting these togerther, we have the following codes.
C (0 ms)
1 int findMin(int* nums, int numsSize) { 2 int l = 0, r = numsSize - 1; 3 while (l < r && nums[l] > nums[r]) { 4 int mid = (l & r) + ((l ^ r) >> 1); 5 if (nums[mid] > nums[r]) l = mid + 1; 6 else r = mid; 7 } 8 return nums[l]; 9 }
C++ (4 ms)
1 class Solution { 2 public: 3 int findMin(vector<int>& nums) { 4 int l = 0, r = nums.size() - 1; 5 while (l < r && nums[l] > nums[r]) { 6 int mid = (l & r) + ((l ^ r) >> 1); 7 if (nums[mid] > nums[r]) l = mid + 1; 8 else r = mid; 9 } 10 return nums[l]; 11 } 12 };
Python (48 ms)
1 class Solution: 2 # @param {integer[]} nums 3 # @return {integer} 4 def findMin(self, nums): 5 l, r = 0, len(nums) - 1 6 while l < r and nums[l] > nums[r]: 7 mid = (l & r) + ((l ^ r) >> 1) 8 if nums[mid] > nums[r]: 9 l = mid + 1 10 else: 11 r = mid 12 return nums[l]
