题目链接：Leetcode 33. 搜索旋转排序数组

本题将采用二分查找寻找目标值；首先通过对比left、right和mid下标对应的值，可知mid分割的哪一侧是有序的；然后判断target是否属于有序的一侧，若属于，则在有序侧查找，反之，在另一侧查找。

例如，在数组nums = [5,6,7,1,2,3,4]中查找target = 3。此时，下标left = 0、right = 6、mid = 3；因为nums[right] > nums[mid]，则右侧nums[mid: ]是有序的，又因为nums[mid] < target < nums[right]，所以下一轮要在右侧进行查找。

完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution():
    def search(self, nums, target):
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right-left) // 2 # 不采用 (left + right) // 2 是为了防止精度溢出
            if nums[mid] == target: return mid
            if nums[left] <= nums[mid]: # 左边有序[left: mid]
                if target >= nums[left] and target <= nums[mid]: 
                    right = mid
                else:
                    left = mid + 1
            else: # 右边有序[mid+1: right]
                if target >= nums[mid] and target <= nums[right]:
                    left = mid
                else:
                    right = mid - 1
        
        return -1 # 若未找到目标值，返回-1
    
s = Solution()
print(s.search([1,2], 8))