江西省工程建设网站,东莞网络推广服务,做淘宝客的的网站有什么要求,wordpress 打包 转移二分查找,又名折半查找,其搜索过程如下:
从数组中间的元素开始,如果元素刚好是要查找的元素,则搜索过程结束如果搜索元素大于或小于中间元素,则排除掉不符合条件的那一半元素,在剩下的数组中进行查找由于每次需要排除掉一半不符合要求的元素,这需要数组是已经排好序的或者是有…二分查找,又名折半查找,其搜索过程如下:
从数组中间的元素开始,如果元素刚好是要查找的元素,则搜索过程结束如果搜索元素大于或小于中间元素,则排除掉不符合条件的那一半元素,在剩下的数组中进行查找由于每次需要排除掉一半不符合要求的元素,这需要数组是已经排好序的或者是有规律可循的
在二分查找中,对于每一个反馈,我们能过滤掉一半的数据,因此二分查找相对于普通遍历是一个高效的查找算法,其时间复杂度为O(logn),虽然二分查找的思想很简单,然而二分查找的细节可不少,这里根据力扣的题型给出两种二分查找的写法
二分查找基础版 题目链接
使用二分查找的方式在一个升序的数组中找到指定的值并且返回,其代码框架如下:
定义left为左指针,right为右指针,搜索的区域在[left,right]中
搜索目标值为targtwhile(leftright){//得到查找的中点mid(leftright)/2//对于升序数组当前值小于目标值目标值应该在当前值的右侧if(midtarget){左指针右移如今搜索区域变为[mid,right]}else if(midtarget){右指针左移如今搜索区域变为[left,mid]}else{只剩下等于的情况了直接返回结果找到了目标值}
}代码如下
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (right - left) // 2 leftnum nums[mid]if num target:left mid 1elif num target:right mid - 1else:return midreturn -1 注意重点来了注意代码中的几个关键点 while循环中的条件是leftright这意味着在搜索不到答案退出循环时leftright1而在二分查找中我们查找的是[left,right]这个区间这说明所有的数都被搜索到了记住这一点以下我们统称leftright的这种写法为写法一mid(right-left)//2left这个写法其实与mid(leftright)/2效果是一致的这么写的目的是为了防止整形溢出的情况因为leftright相加如果大于整形最大值的话会导致结果异常在移动左右指针时使用的是rightmid-1和leftmid1这是因为mid的值已经在上一轮循环中搜索过了不需要再进行一次搜索二分查找进阶版--寻找左右边界
为了引出二分查找的第二种写法,这里给出一道非力扣题型的二分查找
寻找左侧边界
例如对于数组[1,2,2,2,3],查找目标为2,我们需要返回最左边的2的下标1,如果使用写法一我们的代码看起来是下面这样的:
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (right - left) // 2 leftnum nums[mid]if num target:left mid 1elif num target:right mid - 1else:right mid - 1if(left len(nums) || nums[left] ! target): return -1return left 这段代码有两个注意点: 由于要找到最左侧的边界,在else条件里(numtarget), 我们不再直接返回结果,而是继续的收缩右边界,直到right越界或者找到最左边界坐标是不是决定很奇怪,为什么最后返回的是left,而且是对left做越界判定,记不记得我在之前说过leftright的退出条件是leftright1,我们复盘一下最后一轮循环的情况,你就知道为什么最后返回的是left而且也是对left进行越界的判断了复盘最后一轮循环的过程,对于数组[1,2,2,2,3],target为2,假设当前mid为1,循环也接近了极限,也就是leftmidright1,根据代码,在numtarget2的时候,根据代码rightmid-1,那么最后right是否一定不指向正确的结果1,而left指针还没有被移动,依然指向mid,所以我们最后应该返回left再来看一种情况对于数组[1,2,2,2,3]如果我们查找的是数字4,由于数组中的数字都小于target,我们会不断的缩小左边界,直到退出循环leftright1,此时left一定是越界的,因为right从头到尾都没动过,而leftright1保证了left越界再来看一种情况对于数组[1,2,2,2,3]如果查找的是数字0,由于数组中的数字都大于target,我们会不断的缩小右边界,直到退出循环leftright1,由于我们最后判断的是left指针,即使right指针越界了,leftright1也能保证left刚好在下标0的位置,所以是不需要考虑左侧越界的情况的讲到这里是不是觉得写法一来解决这样的问题真的很复杂,所以我们接下来要说写法二
写法二
使用写法二来解决左侧边界问题,代码如下:
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (right - left) // 2 leftnum nums[mid]if num target:left mid 1else:right midreturn left 注意点如下: while循环结束的条件是leftright,这说明循环退出的条件是leftrightmid,最后的返回值我们这里返回的是left,其实返回right也是可以的,因为循环退出的条件是leftmidright嘛可以看到另一个不同在于在else条件里我们偏移右指针的时候写的是rightmid,我们合并了numtarget和numtarget的条件,所以为什么是写成rightmid而不是rightmid-1呢?leftmid1和rightmid 对于leftmid1可以这么理解,mid此时的值一定不是我们需要的值,所以我们可以直接越过.举个例子对于数组[1,2,3,4,4,5,5],如果要搜索数字5,我们第一个搜索到的数字mid(leftright)/2nums[3]4,此时4target,那么是否一定不是我们需要的结果,那么我们可以直接越过对于rightmid,mid的值可能是我们需要的值,但是在当前循环中我们无法判断出来,所以我们进行保留,举个列子,对于数组[1,5,5,5],如果要搜索数字5,我们第一个搜索到的数字midnums[1]5,此时的5是下标为1的5,并且也是最终我们需要找到的最左侧边界,此时rightmid这行代码就能帮助我们把结果保留了,而后等待left不断右移知道leftright就能退出循环返回最终结果了寻找右侧边界
学会了寻找左侧边界,那么右侧边界是否也很容易理解了,其实这里有一个小坑,还需要填一下,这里先给出寻找右侧边界的代码
class Solution:def search(self, nums: List[int], target: int) - int:left, right 0, len(nums) - 1while left right:mid (right - left 1) // 2 leftnum nums[mid]if num target:right mid - 1else:left midreturn right 相信你已经发现了,在取mid的时候我们在括号里加上了一个1,这是因为程序语言中除法操作后下标向下取整(例如(12)/21),而在寻找右侧边界的过程中,这个操作会导致死循环,永远退不出循环,举个列子:两者相除,向下取整,这个操作是不是说明mid在有些情况下会向左偏向,我们在寻找左侧边界的时候,需要它向左偏向因此能退出循环,而在寻找右侧边界时,需要它向右收缩边界,此时是否就和向下取整这个情况矛盾了,此时一左一右就会导致永远进入死循环了,因此需要mid(right-left1)//2left这个操作来打破这个死循环总结
这里很重要哦,如果理解了这里,就离彻底理解二分写法不远了
写法一适合用于在[left,right]这个范围内找到值,例如最基础的二分写法,这种写法需要判断最后返回的是left还是right,要分析最后一次循环后造成的结果写法二适合用于在[left,right]这个区间内排除值,然后在leftrightmid的时候找到最后的答案,因此写法二的if条件里写的是target值一定不存在的情况在写法二中如果else条件里是leftmid这个条件(趋向是收缩左边界和向下取整相反),需要修改mid为(right-left1)//2left来避免死循环情况的出现
二分搜索代码很简单,但细节是魔鬼,如果觉得自己理解了可以使用写法二做做这一题,题目链接
