一、题目
二、思路
对于有序数组或者部分有序数组，并且注意题目的时间复杂度要求为O ( l o g n ) O(logn)O(logn)，一般使用二分搜索及其变种。
既然数组会经过旋转，则我们不能只是用常规的二分查找，而是需要进行判断，基于先对有序段判断的二分查找。比如当在左边（nums[left]和nums[mid]）这段有序时，要进行分类讨论：
（1）如果target就在这段内，则常规的二分；
（2）如果target不在这段内，那就去另一段（nums[mid+1]和nums[right]）中找target，注意此时的这段整体是无序的（刚才说了我们前提是基于先找有序段中判断），并且target肯定就在这段内，那就可以缩小范围了。
（3）完事后继续while训练
ps：对于右边有序的情况也是一样的。
【注意】
（1）while判断有等号。
（2）while内部判断是否有序的条件也有等号：有可能left和mid相等，如[3, 1] 1。
三、代码
class Solution: def search(self, nums: List[int], target: int) -> int: left ,right = int(0), int(len(nums) - 1) # 二分，此处判断要加上等号 while(left <= right): mid = int((left + right) / 2) if nums[mid] == target: return mid # 左边有序 # 有可能left和mid相等，如[3, 1] 1,所以需要加上等号 if(nums[left] <= nums[mid]): if (nums[left] <= target and target <= nums[mid]): right = mid - 1 else: left = mid + 1 else: # “保证”右边有序 if (nums[mid] <= target and target <= nums[right]): left = mid + 1 else: right = mid - 1 return -1
