33. Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
假设数组是A，左边缘为l，右边缘为r，中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的，那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。
根据以上方法，每次我们都可以切掉一半的数据，所以算法的时间复杂度是O(logn)，空间复杂度是O(1)。
代码如下：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums or not len(nums):
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < nums[right]:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
做题时的感悟:
- 注意边界问题，两个条件左右边界可相等，例如nums[mid] < target <= nums[right] 和 nums[left] <= target < nums[mid]。
- 当第一个判断使用if(A[m] < A[r])时，结果是正确的；而当使用if(A[m] > A[l])时，结果是错误的。因为mid有可能会等于left，所以有可能会跳过第一个判断，所以如果要把left放到前面判断，把判断条件变为A[m] >= A[l]即可。
- 如果数组变成降序该如何处理这道题呢。先判断是升序还是降序，如果这些数字都是不同的，那么采样三个数就可以得出升降序。如果三个数有序，那么很容易判断，剩余的情况是中间低两边高，或者中间高两边低，以中间高的情况为例，那么就是取两边大的那一个，如果在左边，则是递增，如果是右边，则是递减。因为中间一定是最大的数字。中间低两边高的情况类似，类推一下即可。
81. Search in Rotated Sorted Array II
https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/
这道题和Search in Rotated Sorted Array唯一的区别是这道题目中元素会有重复的情况出现。不过正是因为这个条件的出现，出现了比较复杂的case，甚至影响到了算法的时间复杂度。原来我们是依靠中间和边缘元素的大小关系，来判断哪一半是不受rotate影响，仍然有序的。而现在因为重复的出现，如果我们遇到中间和边缘相等的情况，我们就丢失了哪边有序的信息，因为哪边都有可能是有序的结果。假设原数组是{1,2,3,3,3,3,3}，那么旋转之后有可能是{3,3,3,3,3,1,2}，或者{3,1,2,3,3,3,3}，这样的我们判断左边缘和中心的时候都是3，如果我们要寻找1或者2，我们并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。
代码如下：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
if not nums or not len(nums):
return False
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[mid] < nums[right]:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
elif nums[mid] > nums[right]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
right -= 1
return False
做题时的感悟:
移动的指针要与判断边界的指针相同，例如，若判断条件为A[m] < A[r] 和 A[m] > A[r]，此时我们应该移动r指针, r减减。移动l指针也是一样的，不过也要相应的把判断条件改成对l的判断。
153. Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
这道题是变形的Binary Search问题。介绍一个保存min值的方法，这种可以避免跳过r指针，所以可以避免一次判断。而且这个方法可以在Rotated Sorted Array题目中通用。需要找的最小值即是要找边界，所以永远要在无序的那边找。同时要保存一个最小值，同mid来比较。
代码如下：
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or not len(nums):
return -1
import sys
res = sys.maxsize
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
res = min(res, nums[mid])
if nums[mid] < nums[right]:
right = mid - 1
else:
left = mid + 1
return res
154. Find Minimum in Rotated Sorted Array II
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
与Find Minimum in Rotated Sorted Array唯一的区别就是数组里可能有重复元素，即上一道题中解法稍作变形即可。
代码如下：
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums or not len(nums):
return -1
import sys
res = sys.maxsize
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
res = min(res, nums[mid])
if nums[mid] < nums[right]:
right = mid - 1
elif nums[mid] > nums[right]:
left = mid + 1
else:
right -= 1
return res
