LeetCode50天刷题计划（Day 18—— 搜索旋转排序数组（8.50-12.00）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 前言
• 一、题目
• 二、思路
• 三、代码
• • 1.有错误，但未知
  • 2.AC(python)
  • 3.二分查找的代码
• 总结

没见过的二分搜索题捏

一开始看到题把他想的有点复杂，觉得要不要把数组再转回去之类的，后来发现只是一个部分有序序列的搜索问题。搜索算法最多的时间复杂度就是O（n），即遍历，想要优化为题中要求的O（logn），就需要二分查找了。以下是部分有序序列的二分查找解法：
二分搜索的核心在于每次可以丢弃一半的数据，以此达到减小时间复杂度的目的，在本题中也是这样。不难看出，每次取中点的时候，其左右两边的序列都是一半有序一半无序的，（通过区间首尾元素大小判断：有序区间首元素一定小于尾元素，无序区间首元素一定大于尾元素）。此时需要判断target是否在有序区间数据范围内，若在则丢弃无序区间，若不在则丢弃有序区间。
理论上，如果在一次选择中选择了有序区间，那么之后的查找变为完全的二分查找。
算法用递归实现,注意递归的终止条件有两个，一个是找到了（nums【mid】==target），一个是没找到（down和up指针指向同一个数了，且这个数也不是target（此时仍需一次判断，不要相遇就判定没找到，说不定就在target处相遇了捏）

第一次写递归函数不知道为啥总是过不了，我真无语了，不知道为啥 难道leetcode不能函数嵌套吗，于是又换成while循环写

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        #递归
        def mid_s(down,up): #down低指针，up高指针
            mid=(down+up)//2 #中点下标
            #print(down,mid,up,nums[mid],target)
            if(nums[mid]==target): #终止，找到了
                return mid
            if(down==mid):#只剩两个元素
                if (nums[up] == target):
                    return up
                else: #终止，没找到(仍需判断，在上面
                    return -1
            #如果左半边有序并且target在左半边范围内 或者 右半边有序但target不在右半边范围内,选择左边 
            if(nums[down]<=nums[mid-1] and target>=nums[down] and target<=nums[mid-1] or nums[mid+1]<=nums[up] and (targetnums[up])): 
                mid_s(down,mid-1)
            else:
                mid_s(mid+1,up)
        #调用，返回
        return mid_s(0,len(nums)-1)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        down=0
        up=len(nums)-1
        #递归
        while(True): #down低指针，up高指针           
            mid=(down+up)//2 #中点下标
            #print(down,mid,up,nums[mid-1])
            if(nums[mid]==target): #终止，找到了
                return mid
            if(down==mid):#只剩两个元素
                if (nums[up] == target):
                    return up
                else: #终止，没找到(仍需判断，在上面
                    return -1
            #如果左半边有序并且target在左半边范围内 或者 右半边有序但target不在右半边范围内,选择左边 
            if(mid>0 and nums[down]<=nums[mid-1] and target>=nums[down] and target<=nums[mid-1] or nums[mid+1]<=nums[up] and (targetnums[up])): 
                up=mid-1
            else:
                down=mid+1

比上面的更改了两个地方，首先是while循环中指定条件左边的指针要小于或等于右边
其次是没有在while循环中找到的集中在循环外输出-1，可以避免复杂的终止判定条件。

def search(nums: list[int], target: int) -> int:
    #递归
    down=0
    up=len(nums)
    while(down<=up):#####################################注
        mid=(down+up)//2 #中点下标
        #print(down,mid,up,nums[mid],target)
        if(nums[mid]==target): #终止，找到了
            return mid
        #如果在左半边
        if(target 
总结 
一直debug，太难顶了，二分查找也学的不好QAQ