# 6-lines C/C++/Python Solutions

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

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

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

Fastest C time is 0ms and 90% of submissions reach it. How do you know you're not among the slowest of those? Same for C++ with 4ms.

Maybe it's because you access `nums` so often. It's not necessary to check it in the while condition.

Fastest recent Python time is btw 36ms, and I just managed to achieve that with this solution:

``````class Solution:
findMin = min
``````

First time I've seen `(l & r) + ((l ^ r) >> 1)` actually being used (I only know it from some article). Does it have an advantage over `l + (r - l) / 2`?

• Wow, `findMin = min` is really... nom nom nom :-) I know nothing about such an implementation... I try to write as

``````class Solution:
# @param {integer[]} nums
# @return {integer}
def findMin(self, nums):
return min(nums)
``````

And it takes 50 ms.

For `(l & r) + ((l ^ r) >> 1)`, I just learn it from the code of one of my seniors. And then I keep this golfing habit :-) Well, regarding its advantage, perhaps it involves less arithmetic operations and thus may be faster?

BTW, Stefan, could you please give some hints of how to avoid accessing `nums` in the while condition? Thanks~

• Yeah, I still don't fully know why `findMin = min` works, asked on StackOverflow but haven't taken the time to learn enough to understand it well.

I think `return min(nums)` is about the same speed (except when calling tons of times with tiny inputs), the time difference is just the variance of the judge system.

Heh, `(l & r) + ((l ^ r) >> 1)` is certainly no golfing habit. Maybe an anti-golfing habit :-). Or do you mean something other than code golf, which goes for shortest code?

Here's my solution. My invariant is just that `nums[lo:hi+1]` contains the minimum.

``````def findMin(self, nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
``````

• Haha, I just realized that our solutions are actually exactly the same except for your extra test. So the answer to your question of how to avoid that extra test is literaly "just remove it" :-P

• Hi, Stefan. Well, I just misunderstand code golfing. I originally suppose that it refers to all the unusual habits of writing an easy code, like making it shortest or writing it in a very "strange" way.

Well, your code is much concise. However, aftering removing the extra check in the `while` condition, the code takes more time, from 48ms to now 52ms...

• Yeah, golfing does often get "strange" in order to be short :-)

I just tried submitting yours a couple more times:

• With the check: 52, 48, 56
• Without the check: 40, 48, 36

But three minutes later, this time the other way around:

• Without the check: 56, 72, 44
• With the check: 44, 44, 44

Not exactly reliable...

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.