网站网页制作企,网页版云游戏,深圳注册投资公司的条件,做外贸网站要有域名前言
二分查找的思想是简单易懂的#xff0c;但是在具体实现的时候能被一些细节给逼疯。今天学习了一下二分查找相关的知识与小细节#xff0c;听取同学的推荐#xff0c;参考了大神“灵茶山艾府”的教学视频。
下面就以一道算法题为例子#xff0c;来写一下二分查找的方…前言
二分查找的思想是简单易懂的但是在具体实现的时候能被一些细节给逼疯。今天学习了一下二分查找相关的知识与小细节听取同学的推荐参考了大神“灵茶山艾府”的教学视频。
下面就以一道算法题为例子来写一下二分查找的方法。但这篇博客我会不局限于这道题尽量去着笔于二分查找的算法本身。
原题描述
34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组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 解答
方法一固定套路
思想
其实这道题从有序数组和O(log n)时间复杂度来看很显然需要用到二分查找。
也就是需要用二分查找找到目标元素target出现的第一个位置和最后一个位置。
二分查找在实现的时候根据左右边界开闭区间的不同有三种实现方式闭区间[l, r]、左开右闭(l, r]、开区间(l, r)。
我这里就用闭区间的方式来做但是任何方式其实都是可以的的。
对于查找target的第一个位置其实查找的就是 target的第一个元素在这里将查找 target的函数记作findNotLess()。
但是在找到之后需要判断一下找到的位置是不是合法因为如果这个数组元素都比target小那么找到的位置是超出了数组边界的
还需要判断找到的位置是不是target如果数组中不存在target那么可能找到的是例如target1这样的比target还要大的元素。
像下图所示的例子。 如果经过判断发现target存在数组中并且找到了第一个出现的位置那么如何找target的最后一个的位置
答找最后一个target其实就需要找到 target的第一个元素的位置然后把这个位置-1即可。
也就相当于去找 (target1)的位置然后将找到的下标-1就得到了最后一个target的位置。因为经过刚刚的判断target一定存在那么找到 (targe1)的位置它左边一定是最后一个target
可以发现在找最后一个target时用的是一种偷懒的方法来实现的我把这种方式称作一种固定套路。
因此在非递减顺序排列的int数组中可以在这里进行一下拓展和总结
查找 target的第一个位置直接刚刚所说的findNotLess(target)方法查找 target的第一个位置可以转换成查找 target1也就是findNotLess(target1)查找 target的最后一个位置可以转换成查找 target的第一个位置然后将找到的下标减一。也就是findNotLess(target)-1查找 target的最后一个位置可以转换成查找 target的第一个位置再减一。二次转换成查找 target1的第一个位置再减一也就是findNotLess(target1)-1 注意 上述查找时在查找大于或大于等于一个数的时候都是查找的第一个位置。 在查找小于或小于等于一个数的时候都是查找的最后一个位置。 这是因为在非递减排序数组中查找大于某个数的最后一个数是没意义的一定在数组的最后面。 同样的查找小于某个数的第一个数也是没意义的一定是数组的开头。 代码实现
C代码如下
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int n nums.size();int start findNotLess(nums, target);if(start n || nums[start] ! target)return {-1, -1};int end findNotLess(nums, target1)-1;return {start, end};}int findNotLess(vectorintnums, int target){int n nums.size();int l 0, r n-1;while(l r){int mid l (r-l)/2; // 防止溢出的计算方式if(nums[mid] target)r mid-1; // r1 都是大于等于targetelsel mid1; // l-1都是小于target}return r1; // 返回的是大于等于target的第一个数的下标}
};复杂度分析
时间复杂度
每次都将任务拆分成了之前的一半O(logn)
空间复杂度
没有额外的空间开销O(1)
方法二灵活应用
思想
灵活应用的时候就是不仅仅只用方法一中的FindNotLess()函数在查找出现的最后一个target的时候通过更改函数中的比较方式来进行实现。 也就是下面这一部分
if(nums[mid] target)r mid-1; // r1 都是大于等于target
elsel mid1; // l-1都是小于target在上述代码中这个部分是使得r1都是targetl-1都是target。用这种方式在结束的时候r1的位置就是第一个target假设target存在数组中
我们需要改成l-1都是targetr1都target这样结束的时候l-1的位置就是最后一个target。修改过后的代码见下。
代码实现
C代码如下 其中find_left()函数就是上面的findNotLess()函数。
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int n nums.size();int start find_left(nums, target);if(start n || nums[start] ! target)return {-1, -1};int end find_right(nums, target);return {start, end};}int find_right(vectorint nums, int target){int n nums.size();int l 0, r n-1;while(l r){int mid l (r-l)/2;if(nums[mid] target) // 注意这个地方的不同l mid1;elser mid-1;}return l-1; // 返回的是target的最后一个数}int find_left(vectorintnums, int target){int n nums.size();int l 0, r n-1;while(l r){int mid l (r-l)/2;if(nums[mid] target)r mid-1; // r1 都是大于等于targetelsel mid1; // l-1都是小于target}return r1; // 返回的是大于等于target的第一个数的下标}
};
复杂度分析
时间复杂度
O(logn)
空间复杂度
O(1)
