Leetcode 153: Find Minimum in Rotated Sorted Array

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

My original code:

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if nums is None or len(nums) == 0:
            return None
        if len(nums)== 1:
            return nums[0]
        
        
        left, right = 0, len(nums)-1
        
        while left < right-1:
            mid = (left+right)/2
            if nums[left] < nums[mid] and nums[mid] > nums[right]:
                left = mid
            elif nums[left] > nums[mid] and nums[mid] < nums[right]:
                right = mid
            else:
                left = right = 0
                
        return min(nums[left], nums[right])

My original idea:

A rotated array has a property: if you do binary search by having `left`, `mid` and `right` pointers, if  nums[left] < nums[mid] and nums[mid] > nums[right], that means the left part is intact and the minimum has been rotated to `nums[mid:right+1]`. Similarly, if nums[left] > nums[mid] and nums[mid] < nums[right]  , that means the right part is intact and the minimum has been rotated to `nums[0:mid+1]`. However, in the code above, I didn’t set `left` and `right` to `mid+1` and `mid-1` as in standard binary search because I was afraid that after excluding the current element `nums[mid]`, I may let the whole subarray being without rotation. I thought my algorithm will not work if the array is in a correct format. For example, if we always set `left` to `mid+1`:

input: [3412]

iteration 0: left=0, right=3, mid=1

iteration 1: left=2, right=3. Now nums[left:right+1] is [12] which has correct order

 

But later I find I can safely set `left` and `right` to `mid+1` and `mid` to not exclude the minimum in `nums[left:right+1]`. As long as the minimum is in `nums[left:right+1]`, the algorithm can finally find the minimum. This can be done by:

setting `left` to mid+1 if nums[mid] > nums[right]. 

setting `right` to mid if nums[left] > nums[mid].

So the more concise code can be (https://leetcode.com/discuss/63514/9-line-python-clean-code): 

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        j = len(nums) - 1
        while i < j:
            m = i + (j - i) / 2
            if nums[m] > nums[j]:
                i = m + 1
            else:
                j = m
        return nums[i]