【LeetCode】33. 搜索旋转排序数组

1.题目

其实这题挺难的。

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 # 返回下标