温州最便宜网站建设,分类达人介绍,常见的网站推广途径,超简单手工小制作题目
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣#xff08;LeetCode#xff09;
思路
查找左边界
初始化 left 0, right nums.size() - 1
当 left right 时循环#xff1a;
计算中点 mid left (right - left) / 2
如果 nums[mid] target…题目
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
思路
查找左边界
初始化 left 0, right nums.size() - 1
当 left right 时循环
计算中点 mid left (right - left) / 2
如果 nums[mid] target目标在右侧left mid 1
否则目标在左侧或当前位置right mid
循环结束后left right检查 nums[left] 是否等于 target
查找右边界
初始化 left 0, right nums.size() - 1
当 left right 时循环
计算中点 mid left (right - left 1) / 2 向上取整
如果 nums[mid] target目标在左侧right mid - 1
否则目标在右侧或当前位置left mid
循环结束后left right检查 nums[left] 是否等于 target
图解过程
以数组 [5, 7, 7, 8, 8, 10]目标值 target 8 为例
查找左边界
初始状态
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑ ↑left right 第一次迭代
mid 0 (5-0)/2 2
nums[mid] 7 8目标在右侧
left mid 1 3
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑ ↑left right 第二次迭代
mid 3 (5-3)/2 4
nums[mid] 8 8目标可能在左侧
right mid 4
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑ ↑left right 第三次迭代
mid 3 (4-3)/2 3
nums[mid] 8 8目标可能在左侧
right mid 3
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑leftright 循环结束
left right 3循环结束
nums[left] 8 target找到左边界 begin 3
查找右边界
初始状态
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑ ↑left right 第一次迭代
mid 0 (5-01)/2 3 向上取整
nums[mid] 8 8目标可能在右侧
left mid 3
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑ ↑left right 第二次迭代
mid 3 (5-31)/2 5 向上取整
nums[mid] 10 8目标在左侧
right mid - 1 4
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑ ↑left right 第三次迭代
mid 3 (4-31)/2 4 向上取整
nums[mid] 8 8目标可能在右侧
left mid 4
索引: 0 1 2 3 4 5
数组: [5, 7, 7, 8, 8, 10]↑leftright
循环结束
left right 4循环结束
nums[left] 8 target找到右边界 end 4
最终结果
返回 [begin, end] [3, 4]表示目标值 8 的第一个位置是索引 3最后一个位置是索引 4。
关键点
使用 left right 作为循环条件确保循环结束时 left right查找左边界时使用向下取整计算 mid更新方式为 right mid查找右边界时使用向上取整计算 mid更新方式为 left mid循环结束后检查 nums[left] 是否等于目标值
读者可能会出现的错误写法
class Solution {
public:vectorint searchRange(vectorint nums, int target) {if(nums.empty()){return {-1,-1};}int left 0;int right nums.size()-1;int begin -1;int end -1;while(left right){int mid left (right-left)/2;if(nums[mid]target){left mid 1;}else{right mid-1;}}if(nums[left] target){begin left;}left 0;right nums.size()-1;while(left right){int mid left (right-left)/2;if(nums[mid] target){right mid-1;}else{left mid1;}}if(nums[right] target){end right;}return {begin,end};}
};
在查找左边界的时候right mid而不是right mid-1;在查找右边界的时候left mid而不是left mid1,并且leftright 而不是leftright,并且当leftmid的条件下mid left (right-left1)/2,而不是mid left (right-left)/2 为什么要用right mid而不是right mid - 1 如果nums[mid] targetmid可能就是我们要找的左端点或者左端点在mid左侧
如果我们使用right mid - 1就可能错过正确答案
使用right mid可以保留mid作为可能的答案同时继续向左搜索 为什么我们使用right mid - 1就可能错过正确答案 假设数组中有多个相同的目标值例如[1, 3, 3, 3, 5]目标值target 3。
当我们找到一个nums[mid] target时例如中间的那个3我们不知道这是不是第一个出现的3。有两种可能
当前找到的这个3就是第一个3在mid左侧还有其他的3
使用right mid - 1的问题
如果当前找到的nums[mid] target恰好是第一个出现的目标值那么使用right mid - 1会将搜索范围缩小到mid左侧完全排除了mid这个位置。
具体例子
数组[1, 2, 3, 4, 5]target 3
初始left 0, right 4
第一次迭代mid 2, nums[mid] 3 target
如果使用right mid - 1区间变为[0, 1]
但索引2处的元素值为3是我们要找的答案我们已经排除了它
后续迭代会在[0, 1]范围内搜索但这个范围内没有值为3的元素
最终会得出错误结论认为数组中不存在目标值
使用right mid的优势
当nums[mid] target时使用right mid
将右边界移动到mid而不是mid-1
保留了mid作为可能的答案
同时继续在左侧搜索是否有更早出现的目标值
这样即使当前的mid就是第一个目标值我们也不会错过它因为
如果左侧没有其他目标值循环最终会收敛到这个位置
如果左侧有目标值我们会找到那个更早的位置
总结使用right mid - 1在找到目标值时会完全排除当前位置如果当前位置恰好是第一个目标值就会错过正确答案。而right mid保留了当前位置作为候选答案同时继续向左搜索可能存在的更早出现的目标值。 为啥查找左端点的mid算法和查找右端点的mid算法不一样 考虑当搜索区间缩小到只有两个元素时例如 [3, 4]
left 3, right 4mid 3 (4-3)/2 3向下取整如果 nums[mid] target执行 left mid 3新的搜索区间仍然是 [3, 4]下一次迭代mid仍然是3如果 nums[mid] target又执行 left mid 3搜索区间永远是 [3, 4]无法进一步缩小陷入死循环
使用向上取整的解决方案
使用向上取整 mid left (right - left 1) / 2 可以解决这个问题
left 3, right 4mid 3 (4-31)/2 4向上取整如果 nums[mid] target执行 right mid - 1 3搜索区间变为 [3, 3]循环结束
或者如果 nums[mid] target执行 left mid 4区间变为 [4, 4]循环也会结束。 为什么查找左端点不需要向上取整 关键在于更新策略的不同
查找左端点时
当 nums[mid] target 时使用 left mid 1
这个 1 确保了即使 mid left区间也会缩小
查找右端点时
当 nums[mid] target 时使用 left mid没有 1
如果 mid left区间不会缩小导致死循环
总结
查找左端点时即使使用向下取整也不会导致死循环因为
当 nums[mid] target 时left mid 1 会缩小区间
当 nums[mid] target 时right mid 会缩小区间因为 mid ≤ right
查找右端点时使用向下取整可能导致死循环因为
当 nums[mid] target 且 mid left 时left mid 不会缩小区间 当使用right mid和left mid这种更新方式时循环条件应该是while(left right)而不是while(left right)。为啥呀 原因如下
主要原因避免死循环
如果使用while(left right)作为循环条件当left right时循环仍会继续执行
当left right时无论使用什么mid计算方式都会得到mid left right
此时
如果执行right mid结果是right left区间不变
如果执行left mid结果是left right区间不变
下一次循环条件left right仍然满足因为left right
区间没有缩小算法陷入死循环
具体例子
假设数组[1, 3, 5]当搜索区间缩小到[1, 1]即left right 1
如果使用while(left right)
mid 1
如果执行right mid区间仍为[1, 1]
如果执行left mid区间仍为[1, 1]
下一次循环条件仍然满足陷入死循环
正确的写法
class Solution {
public:vectorint searchRange(vectorint nums, int target) {if(nums.empty()){return {-1,-1};}int left 0;int right nums.size()-1;int begin -1;int end -1;while(left right){int mid left (right-left)/2;if(nums[mid]target){left mid 1;}else{right mid;}}if(nums[left] target){begin left;}left 0;right nums.size()-1;while(left right){int mid left (right-left 1)/2;if(nums[mid] target){right mid-1;}else{left mid;}}if(nums[right] target){end right;}return {begin,end};}
};
