1. Find minimum in rotated sorted array()

解题思路： L为array左端，R为array右端，M = (L+R)/2，若num[M] > num[R], 则说明rotated的部分在右边，最小值为M+1 ~ R中的一个元素。若num[M] < num[R], 则说明rotated的部分在左边，L ～ M中的一个元素可能为最小值。

1   def findMin(self, num): 2     lenNum = len(num) 3     L = 0 4     R = lenNum - 1 5     while L < R and num[L] > num[R]: 6       M = (L+R)/2 7       if num[M] > num[R]: 8         L = M + 1 9       else:10         R = M11     return num[L]

2. Find Minimum in Rotated Sorted Array II()

解题思路：此题与上一题的不同之处在于数组里有重复的数字。判定条件需要变一下，如果num[L] >= num[R]则存在rotated， =号的存在就是由于有重复的数字。若出现num[M] == num[R]或num[L] == num[M]的情况，均不能判定M～R或L～M之间是否存在rotated，因此L++, 只判定不等于的情况。

1   def findMin(self, num): 2     lenNum = len(num) 3     L = 0 4     R = lenNum - 1 5     while L < R and num[L] >= num[R]: 6       M = (L + R)/2 7       if num[M] > num[R]: 8         L = M + 1 9       elif num[M] < num[L]:10         R = M11       else:12         L += 113     return num[L]

3. Search In Rotated Sorted Array()

解题思路：二分法

1   def search(self, A, target): 2     lenN = len(A) 3     l = 0 4     r = lenN - 1 5     while l <= r: 6       m = (l+r)/2 7       if A[m] == target: 8         return m 9       if A[l] <= target < A[m]:10         r = m - 111       elif A[m] < A[r] and (target < A[m] or target > A[r]):12         r = m - 113       else:14         l = m + 115     return -1

4. Search In Rotated Sorted Array II()

解题思路：A[L] < A[M]才表示右边部分rotated，若A[L] == A[M]，则不能保证一定是右边部分rotated，此时L+= 1

1   def search(self, A, target): 2     lenN = len(A) 3     l = 0 4     r = lenN - 1 5     while l <= r: 6       m = (l+r)/2 7       if A[m] == target: 8         return True 9       if A[l] < A[m]:10         if A[l] <= target < A[m]:11           r = m - 112         else:13           l = m + 114       elif A[l] > A[m]:15         if A[m] < target <= A[r]:16           l = m + 117         else:18           r = m - 119       else:20         l += 121     return False