【LeetCode每天一题】Search in Rotated Sorted Array（在旋转数组中搜索）
Suppose an array sorted in ascending order 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]).You are given a target value to search. If found in the array return its index, otherwise return -1.You may assume no duplicate exists in the array.Your algorithm's runtime complexity must be in the order of O(log n).
Example 1: Input: nums = [4,5,6,7,0,1,2] , target = 0 Output: 4
Example 2: Input: nums =[4,5,6,7,0,1,2] , target = 3 Output: -1
思路
这道题的主要思路我们可以利用二分查找的办法来解决问题，只不过相对于普遍性二分查找，旋转数组的情况会稍微复杂一些，主要是在缩小边界的判断上。如果nums[middle] 大于nums[start]时，我们还需要更具target和nums[start]、nums[middle]的大小关系来决定移动左边的指针还是移动右边的指针。
时间夫复杂度为O(nlog n),空间复杂度为O(1)。
图示
解决代码
1 class Solution:
2 def search(self, nums, target):
3 """
4 :type nums: List[int]
5 :type target: int
6 :rtype: int
7 """
8 if not nums:
9 return -1
10 start, end = 0, len(nums)-1
11 while start <= end: # 循环条件
12 middle = start+((end-start)>>1) # 求中间值
13 if nums[middle] == target: # 找到直接返回下标
14 return middle
15 elif nums[start] <= nums[middle]: # 先判断nums[start] 和nums[middle]的关系
16 if nums[start] <= target and target < nums[middle]: # 在判断start和middle对应元素与target的关系，决定相应指针移动方向
17 end = middle -1
18 else:
19 start = middle + 1
20 else:
21 if nums[middle] < target and target <= nums[end]: # 判断之间的关系middle和end对应元素yutarget之间的关系。
22 start = middle + 1
23 else:
24 end = middle -1
25 return -1 # 没有找到，返回-1