其实这题挺难的。
2.思想拿到这道题时，我首先考虑的问题是：
- 找到数组的旋转分界线，然后这样我们就可以还原数组（得到一个有序的数组），然后根据二分查找再来迅速定位。
但问题是：是否有必要找到数组的旋转分界线？ 其实是没有必要的。那么有没有其它的方法解决这个问题呢？
传统的二分类中，我们都使用mid 下标处的值作为判断依据，但是那是在一个完全有序的数组中是成立的，如果一个数组并非完全有序，那么还有什么其它的判断方法吗？例如本题中，题目给定的条件是：数组原本是有序的，经过一个旋转操作变成了无序，那么在查找的时候，我们可以知道其实 [left,mid-1],[mid,right]中必有一个是有序的数组。举个例子：在数组中[6,7,1,2,3,4,5]，我们枚举任意一个下标的数，都会发现由mid划分成的两个区间满足至少有一个区间是有序的，根据这个特性，我们便可以得到一个复杂版的二分法。再分别在这两个子区间内做分析，问题就迎刃而解。
3.代码可AC的代码如下：
class Solution:
# 得到
def search(self, nums: List[int], target: int) -> int:
left ,right = 0, len(nums)-1
while(left <= right):
mid = (left + right) // 2
if nums[mid] == target: # 这里先比较就避免了后面两次再比较
return mid
if left == mid:
left = mid+1
continue
# 至少有一端是有序的
# 先判断有几个数，左侧是否有序
if nums[left] <= nums[mid-1]:
if nums[left] <= target and target <=nums[mid-1]: # 在下面这个区间二分查找
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
下面这段代码是我的第一印象想法，
class Solution:
def search(self, nums: List[int], target: int) -> int:
bound_idx = get_bound(nums)
if bound_idx == 0:
else:
def get_bound(self,nums):
idx = 1
if len(nums) > 1 :
if nums[idx] > nums[idx-1]: # 前两个数满足升序
else:
return idx-1 # 直接返回0
nxt = idx << 1 # 左移一位
while(idx < len(nums) and nums[idx] < nums[nxt]):
idx = nxt
# 说明在区间 [idx,nxt] 中是存在一个
return idx # 返回下标
