LeetCode解题之Search in Rotated Sorted Array
原题
把一个严格升序的数组进行旋转，如[0,1,2,3,4,5]旋转3位成为[3,4,5,0,1,2]。在这样的数组中找到目标数字。如果存在返回下标，不存在返回-1。
注意点：
- 数组中不存在重复的数字
- 不知道数组旋转了多少位
例子：
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 6
输出: 2
输入: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
输出: -1
解题思路
采用了二分搜索，不过旋转后的数组要讨论的情况增多了。其实旋转后的数组的大小关系一般如下图：
/
/
/
/
/
/
/先通过中点与左顶点的关系来分类讨论中点落在了哪一部分，如果在左半边，则继续讨论目标数在中点的左边还是右边；如果在右半边，同样讨论目标数的位置。同时需要注意特殊情况只剩下两个数时，例如[3,1]，这时求出的中点也是3，如果中点不匹配，应考虑1。这种情况不好与上面的情况合并，单独列出。
AC源码
class Solution(object):
def search(self, nums, target):
""" :type nums: List[int] :type target: int :rtype: int """
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] > nums[left]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < nums[left]:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
left += 1
return -1
if __name__ == "__main__":
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 4) == 0
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 7) == 3
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 2) == 6
assert Solution().search([3, 1], 3) == 0
assert Solution().search([3, 1], 1) == 1欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源码。