题目

Suppose a sorted array 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.

思路

个人觉得这是一道值得回味的二分法题目。与给出target的二分法搜索比，这道题目的target是未知的，并且array是rotated。我个人是从观察给出的例子入手的。

1. 最小值是唯一一个比它左右相邻数字都小的数字

2. 当中位数比start 和 end 都大的时候，最小值在右边

3. 当中位数比start 和 end 都小的时候，最小值在左边

4. 当中位数比start大，比end小的时候，我们进入了sorted的array，最小值也是在左边

那么我们做这道题目的目的，就是通过2，3这两步，进入最小值所在的sorted的array，从而进行第4步。我本人走的弯路是，过于专注于1，从而逻辑变得复杂。其实2，3，和4步就可以帮助我们顺利找到最小值。

代码

class Solution:    # @param nums: a rotated sorted array    # @return: the minimum number in the array    def findMin(self, nums):        # write your code here        if nums is None or len(nums) == 0:            return -1        start = 0        end = len(nums) - 1        while start + 1 < end:            mid = start + (end - start) / 2            if nums[mid] > nums[end]:                start = mid            elif nums[mid] < nums[start] or (nums[mid] < nums[end] and nums[mid] > nums[start]):                end = mid        return nums[start] if nums[start] < nums[end] else nums[end]

体会

这道题目的个人体会就是如果用二分法处理sorted array，核心逻辑在于把已知input分为左右两部分，再从中入手。