• 39.1%

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/#/description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

1. nums[left] < nums[right], 返回的结果就是nums[left]
2. nums[left] > nums[right]相对复杂一些。对于数组里只有两个的话，只要返回第二个就好了。否则，针对两种中间情况进行讨论就好了。

4ms, 21.69%, June.19th, 2016

https://leetcode.com/discuss/13389/compact-and-clean-c-solution

Compact and clean C++ solution

Classic binary search problem.

Looking at subarray with index [start,end]. We can find out that if the first member is less than the last member, there’s no rotation in the array. So we could directly return the first element in this subarray.

If the first element is larger than the last one, then we compute the element in the middle, and compare it with the first element. If value of the element in the middle is larger than the first element, we know the rotation is at the second half of this array. Else, it is in the first half in the array.

Welcome to put your comments and suggestions.

Some corner cases will be discussed here

https://discuss.leetcode.com/topic/14768/4ms-simple-c-code-with-explanation

4ms simple C++ code with explanation

In this problem, we have only three cases.

Case 1. The leftmost value is less than the rightmost value in the list: This means that the list is not rotated.

e.g> [1 2 3 4 5 6 7 ]

Case 2. The value in the middle of the list is greater than the leftmost and rightmost values in the list.

e.g> [ 4 5 6 7 0 1 2 3 ]

Case 3. The value in the middle of the list is less than the leftmost and rightmost values in the list.

e.g> [ 5 6 7 0 1 2 3 4 ]

As you see in the examples above, if we have case 1, we just return the leftmost value in the list. If we have case 2, we just move to the right side of the list. If we have case 3 we need to move to the left side of the list.

Following is the code that implements the concept described above.

https://discuss.leetcode.com/topic/5044/simplest-and-fastest-c-solution-o-lg-n-you-can-t-beat-this

Simplest and fastest C++ solution O(lg N), you can’t beat this!

Binary search: basically eliminate the impossible elements by half each time by exploiting the sorted property.

https://discuss.leetcode.com/topic/6112/a-concise-solution-with-proof-in-the-comment

A concise solution with proof in the comment

https://discuss.leetcode.com/topic/26884/9-line-python-clean-code

9-line python clean code

Just use binary search

Solution Mine:

52ms, 50.58%, June.19th, 2016

Solution Mine:

64ms, 18.65%, June.19th, 2016

Solution 1:

56ms, 34.04%, June.19th, 2016

https://leetcode.com/discuss/63514/9-line-python-clean-code