Python|Python 每日一练二分查找搜索旋转排序数组详解蓝桥杯|python|算法|排序算法|

文章图片
大一在读大数据管理与应用专业欢迎交流

文章图片
备战蓝桥杯倒计时71天

文章图片
目前主要学习Python算法与数据结构今日主题：二分查找

文章图片
算法人算法魂算法题让我们敢于挑战自己做意想不到的事情
如果还没接触过二分查找的可以看一下小郑上一篇博客保证入门简简单单(有模板)（属于优化版适用很多场景但今天这道题用起来就相形见绌了）
今天这个二分写法与上面的模板有所不同是最基本的写法很简单对吧

#核心框架 while a<=b: mid=(a+b)//2 if nums[mid]==target： return mid elif nums[mid]>target: b=mid-1 else: a=mid+1

现在来让我们试试手

问题描述：
文章图片

如果你觉得比较难？先看看这种方法

Python 自带函数解法：index函数用法传送门Python List index()方法 | 菜鸟教程 (runoob.com)
文章图片
https://www.runoob.com/python/att-list-index.html

class Solution: def search(self, nums: List[int], target: int) -> int: return nums.index(target) if target in nums else -1

文章图片

文章图片
二分查找法
文章图片
：

文章图片
你肯定会说 ''这是无序的！！二分查找只能用于有序数组 ''

对的二分查找的确只能用于有序数组
但是审题后我们会发现：nums是由升序数组旋转得到（旋转规则根据题意可知）

先说结论旋转后的数组指针定在任意一个位置那么两段序列中至少有一段是升序的

文章图片
（我知道你有点不完全相信我！！）

但事实就是如此：
文章图片

第一行是未旋转的升序序列第二行是旋转后的
当指针指向中间有两段升序序列
当指针指向右边（2）2到n-1是升序的 n到2不是升序的因此有一段升序序列
当指针指向左边（n+1）n到n+1是升序的 n+1到n-1不是升序的因此有一段升序序列
所以说明上面的结论是正确的（或许你可能觉得我这样证明还不严谨）
那下面给出严格证明：假设数列元素>2个（一个旋转了还是本身）
设k为分界点下标0-k升序下标k-len(nums)-1升序对数列进行旋转
旋转后指针指向k 旋转数列有两段升序序列指向指向>k的位置 k右半边是有序证明完毕

文章图片
代码设计思路：拿到旋转后的数组划分区域：有序的无序的
对有序的二分查找如果找到大功告成
如果找不到返回第一步再次对第一轮的无序区域划分有序区域和无序区域
发现了吗？这其实就是一个递归的过程因此我们设置两个指针l和r 用来递归每一次的无序区间

class Solution: def search(self, nums: List[int], target: int) -> int: def Binary_search(l,r,target): if l==r and nums[l]!=target:return -1 mid=(l+r)//2#至少有一段是完全递增的 if nums[mid]target: b=middle-1 else: a=middle+1 return Binary_search(l,mid-1,target)#如果右有序区间没找到去找左无序区间 else:#有序区间在左,对其对分查找 a,b=l,mid while a<=b: middle=(a+b)//2 if nums[middle]==target: return middle elif nums[middle]>target: b=middle-1 else: a=middle+1 return Binary_search(mid+1,r,target)#如果左有序区间没找到去找右无序区间 return Binary_search(0,len(nums)-1,target)