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

---

前言

没见过的二分搜索题捏

一、题目

二、思路

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

三、代码

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

1.有错误，但未知

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 (target<nums[mid+1] or target>nums[up])): 
                mid_s(down,mid-1)
            else:
                mid_s(mid+1,up)
        #调用，返回
        return mid_s(0,len(nums)-1)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.AC(python)

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 (target<nums[mid+1] or target>nums[up])): 
                up=mid-1
            else:
                down=mid+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.二分查找的代码

比上面的更改了两个地方，首先是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<nums[mid]): 
            up=mid-1
        else:
            down=mid+1
    return -1 #没找到#################################注
print(search([0,1,2,4,5,6,7],5))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

总结

一直debug，太难顶了，二分查找也学的不好QAQ