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 just `nums[l]`

. Otherwise, we reduce the search range by a half each time via comparisons between `nums[l], nums[r]`

and `nums[(l + r) / 2]`

, denoted as `nums[mid]`

:

- 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`

; - If
`nums[mid] <= nums[r]`

, then the minimum is at least`nums[mid]`

and elements right to`mid`

cannot be the minimum. So update`r = mid`

(note that it is not`mid - 1`

since`mid`

may 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 (0ms)**

```
int findMin(int* nums, int numsSize) {
int l = 0, r = numsSize - 1;
while (l < r && nums[l] > nums[r]) {
int mid = (l & r) + ((l ^ r) >> 1);
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid;
}
return nums[l];
}
```

**C++ (4ms)**

```
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r && nums[l] > nums[r]) {
int mid = (l & r) + ((l ^ r) >> 1);
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid;
}
return nums[l];
}
};
```

**Python (48ms)**

```
class Solution:
# @param {integer[]} nums
# @return {integer}
def findMin(self, nums):
l, r = 0, len(nums) - 1
while l < r and nums[l] > nums[r]:
mid = (l & r) + ((l ^ r) >> 1)
if nums[mid] > nums[r]:
l = mid + 1
else:
r = mid
return nums[l]
```

A final remark, I don't know why this algorithm gives almost best running time for C and C++ but just medium performance for Python.