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]:

1. If nums[mid] > nums[r], then mid is in the first larger half and r is in the second smaller half. So the minimum will be right to mid, update l = mid + 1;
2. If nums[mid] <= nums[r], then the minimum is at least nums[mid] and elements right tomid cannot be the minimum. So update r = mid (note that it is not mid - 1 since midmay 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
     
      & 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 + 110             else:11                 r = mid12         return nums[l]