网站集约化建设意见,代码需求网站,wordpress用户上传资源验证,php记录网站访问次数优选算法系列 文章目录 优选算法系列前言一、二分查找的思想二、算法使用小总结 三、代码实现四、二分查找拓展4.1、查找第一次出现的target小总结 4.2、target最后出现的位置小总结 五、代码总结 前言
在这篇博客中#xff0c;我会给大家分享二分查找及其扩展。
这是链接-我会给大家分享二分查找及其扩展。
这是链接-Leetcode二分查找 我们先以常规二分查找来引入。 一、二分查找的思想 接下来的讲解我们以这个例题为背景来展开叙述。链接已放置上方。 例 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
示例 1: 输入: nums [-1,0,3,5,9,12], target 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4 示例 2: 输入: nums [-1,0,3,5,9,12], target 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1 提示 1.你可以假设 nums 中的所有元素是不重复的。 2.n 将在 [1, 10000]之间。 3.nums 的每个元素都将在 [-9999, 9999]之间。 对于上面那题如果我们使用暴力查找当数据量比较大时查找效率时比较低的而且还没有利用题中给除的数组有序这个条件。 二分查找的思想是比较简单的对于有序的数据我们在查找某一值时 首先选择数组中间的数字和需要查找的目标值比较 如果相等最好就可以直接返回答案了 如果不相等: 1.如果中间的数字大于目标值则中间数字向右的所有数字都大于目标值全部排除 2.如果中间的数字小于目标值则中间数字向左的所有数字都小于目标值全部排除 二分法就是按照这种方式进行快速排除查找的。接下来我们对上面例题使用二分思想进行画图解决。
二、算法使用
开始时设left为数据左指针right为数据右指针mid为中间值指针target为目标值。 注以下标作为指针进行计算。 mid(leftright)/2,此时 讲mid指针指向值于目标值比较我们发现该值小于目标值因为数组有序所以mid指针左侧值都小于目标值这时我们更行left指针因为我们知道mid及其左侧值均已小于目标值所以 leftmid1; 再次进行查找 mid(leftright)/2,此时 再次与目标值进行比较发现仍小于目标值再次更新left指针 leftmid1再次查找 mid(leftright)/2,此时 将mid指向值与target进行比较发现与目标值相等循环结束。 这是查找是目标值存在的情况下那么如果目标值不存在呢接下来我们继续分析. 对与上面相同过程我们就不赘述了。 我们接着将mid指向的值与target比较发现指向值大于目标值此时我们可以确定mid右侧值都大于目标值这时我们就该更新右侧指针right。 rightmid-1; 这时我们就没有继续下去的必要了因为left已经大于right了。那么当两个指针相等时我们还要继续判断吗我们就制造除一个这样的场景看看吧。刚好你可以再梳理一遍过程。
首先进入循环 mid(leftright)/2,此时 接着将mid指向值与target比较发现小于target舍弃mid及左边值。更新left ,leftmid1,再次进入循环 mid(leftright)/2,此时 继续比较更新left,leftmid1此时我们想要的场景就来了更行left后 这时就出现了当leftright时我们是否继续循环的情况结果很明显吧对于这两个指针指向的值我们并不能将他排除掉所以当然要再次进入循环了。
小总结
循环结束条件左指针处在右指针的右边时leftright 细节问题: 1、在有的情况下我们使用mid(leftright)/2来对指针取中时,如果left与right相加数值较大时(int类型存不下)可能会发生数据截断,这时我们往往采用mid(right-left)/2right,来代替上面的方式,至于为什么可以代替,大家举两个示例,计算一下就可以知道. 2、上一条提到的mid(right-left)/2left,也许你在其他地方见过mid(right-left1)/2left这种写法,对于普通的二分查找,这两种写法并没有本质的区别,在下面我们会展开讲解
对于普通该念的二分查找我们必须要求查找数据有序。
三、代码实现
int search(vectorint nums, int target) {int left0,rightnums.size()-1;while(leftright)//循环继续的条件{int midleft(right-left)/2;if(targetnums[mid])leftmid1;//小于目标值跟新左指针else if(targetnums[mid])rightmid-1;//大于目标值更新右指针else return mid;//找到直接返回结束循环}return -1;//未找到返回-1}对于很多新手来说大家往往被老师说的数组有序给限制了大家思考一下我们为什么可以一次排除一半的数据呢这是因为我们可以从数据中选取一个值这个值可以将数据分为两部分针对这里来说就是我们可以时刻保证左边比目标值小或右边比目标值大而这个性质被称为二段性。其实对于可以将数据分为两部分的我们都可以考虑它是否可以使用二分来解决。
四、二分查找拓展
Leetcode在排序数组中查找元素的第一个和最后一个位置 接下来我们以这个题为背景来讲解 例 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1 输入nums [5,7,7,8,8,10], target 8 输出[3,4] 示例 2 输入nums [5,7,7,8,8,10], target 6 输出[-1,-1] 示例 3 输入nums [], target 0 输出[-1,-1] 提示 0 nums.length 105 -109 nums[i] 109 nums 是一个非递减数组 -109 target 109 这一题我们使用上面讲的方法是无法解决的因为其中含有重复值数组并非绝对有序这时可能有人想利用上面方法找到目标值后将指针向前移动来找第一次出现的位置向后移动来找第二次出现的位置不就可以了吗但是这样的想法当碰到一些特殊场景如目标值为3待查找空间全为3就相当于将数据都遍历一遍这时我们的查找效率就大打折扣了。 上面我们提到可以利用二分查找的原因并不是数组严格有序是因为我们可以从中找取一个值将数据分为两部分即数据具二段性。 对于上面这组数据在查target第一次出现的位置时我们可以利用第一个target将左边变为小于target的右边变为大于等于target的。同理查找最后出现的位置我们利用target将左边变为小于等于target的右边变为大于target的。这样说是很难理解的接下来我们直接画图解题。
4.1、查找第一次出现的target
细节问题会在下面统一总结
首先进入循环 midleft(right-left)/2此时 比较mid指向的值于target的关系发现mid小于target此时我们所选取的值就可以将数据分为两部分 不合法区域一定不含目标值的区域 合法区域目标值存在区域 这种情况我们肯定是将左侧区域排除的那么我们怎么更新左指针呢当然是让他跳出不和法区域了即 leftmid1,此时 这样第一轮循环算是结束了但这时候我们并没有找到目标中所以再次进入循环 midleft(right-left)/2,此时 将mid指向的值与target比较发现相等此时我们并不知道mid指向的位置是否为第一个target的值 但是我们可以确定mid右侧不包含mid的值都大于等于target
所以这时候我们虽然不知到它是否为第一个值但我们可以确定它右侧一定不包含第一次出现的target这时我们就可以更新right rightmid,为是什么这样更新呢因为我们无法将mid排除此时 再次进入循环midleft(right-left)/2,此时 比较target与mid指向的值,发现相等继续更新right,rightmid此时: 这是我们还要进入循环吗很显然不需要了当leftright是我们就可以跳出循环判断他们所指向值是否等于target如果相等我们就找到了那么如果待查找值不存在呢它的结束条件又是什么呢接下来我们继续看 为了大家好理解这次我们以上面的逻辑从头开始。 首先进入循环 midleft(right-left)/2,此时
将mid指向值与target比较发现小于target更新left leftmid1此时
再次进入循环midleft(right-left)/2,此时
比较…更新leftleftmid1,此时 再次进入midleft(right-left)/2,此时 比较…更新…相等了就不要再继续了 服啦我画麻了气死了…啊啊啊。
小总结
1.结束条件leftright当leftright时我们只需结束循环并在循环外进行判断即可。 2.这里不可使用midleft(right-left1)/2,具体原因当我们使用这个对mid进行计算时有可能进入死循环如 当我们次进入循环时计算的mid仍然不变这时我们就会更新right,rightmid…再次循环。 这样就造成了死循环问题。
4.2、target最后出现的位置 因为我们要查找最后一次出现的位置所以要保证左边为小于等于target的右边为大于target的这样如果存在则left最终指向的就是要查找值这里大家也继续在过程中体会吧 进入循环midleft(right-left1)/2这里和上面有点区别后面分析此时 将mid指向值与target比较发现mid指向值满足小于等于targetleftmid,此时 再次进入循环midleft(right-left1/2此时 继续比较此时mid指向值仍然小于等于target再次更新leftmid,此时 进入循环midleft(right-left1)/2此时 将mid指向值于target比较发下大于target更新rightrightmid-1此时
小总结
1.这里不可以使用midleft(right-left)/2来跟新mid不然会造成死循环大家将两次对比记忆。
五、代码
vectorint searchRange(vectorint nums, int target) {vectorintv{-1,-1};int left0,rightnums.size()-1;//初始指针while(leftright){int midleft(right-left)/2;if(nums[mid]target)leftmid1;else rightmid;}if(leftnums.size()nums[left]target) v[0]left;left0;rightnums.size()-1;//重置指针while(leftright){int midleft(right-left1)/2;if(nums[mid]target) leftmid;else rightmid-1;}if(rightnums.size()nums[right]target) v[1]right;return v;}总结
这里并没有将所以可能遇到的情况罗列出来入果大家想尝试可以用下面三种模拟 1.有节果 2.全大于 3.全小于
下面几题可以使用二分思想来解答 1.x的平方根 2.搜索插入位置 3.山脉数组的峰顶索引 4.寻找峰值
