leedcode每日一题：34. 在排序数组中查找元素的第一个和最后一个位置
2021-03-12 19:30
标签：官方 利用 range 转变 back ++ 思路 实现 二分查找 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 进阶： 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1： 输入：nums = [5,7,7,8,8,10], target = 8 输入：nums = [5,7,7,8,8,10], target = 6 输入：nums = [], target = 0 提示： 0 -109 nums 是一个非递减数组 思路：在升序数组中进行查找-->二分查找，但是我们要找开始位置和结束位置，刚开始的思路是想着找到一个，然后再往左找，然后再往右找，但是这样的时间复杂度就会变成O(nlog n) ,还不如直接遍历。因此要转变思路，还是利用二分查找的思想，去查找开始位置和结束位置，将开始位置和结束位置转化为程序思想： 开始位置：第一个等于target的数的位置 结束位置：第一个大于target的数的位置-1 因此，可以写出如下代码： 但是，我们发现代码在判断时略有冗余，如何提高代码的复用性？在查看官方的代码后，我们可以将开始位置和结束位置换一种思路： 开始位置：第一个大于等于target的数的位置 结束位置：第一个大于target的数的位置 此时，我们只需要单独判断等于的情况即可 leedcode每日一题：34. 在排序数组中查找元素的第一个和最后一个位置 标签：官方 利用 range 转变 back ++ 思路 实现 二分查找 原文地址：https://www.cnblogs.com/ttzz/p/14071891.html
输出：[3,4]
示例 2：
输出：[-1,-1]
示例 3：
输出：[-1,-1]
-109
vectorint> searchRange(vectorint>& nums, int target) {
vectorint> result;
int left = searchRange(nums, target,true);
int right = searchRange(nums, target,false);
result.push_back(left);
result.push_back(right);
return result;
}
int searchRange(vectorint>& nums, int target,bool flag){
int low = 0;
int high = nums.size()-1;
int mid;
while(lowhigh){
mid = low + ((high - low) >>1);
if(flag&&nums[mid] == target&&(mid == 0 || nums[mid-1] != target)){
return mid;
}else if(!flag&&nums[mid] == target&&(mid == nums.size()-1 || nums[mid+1] != target)){
return mid;
}else if(nums[mid] == target&&flag){
high--;
}else if(nums[mid] == target&&!flag){
low++;
}
else if(targetnums[mid]){
high = mid-1;
}else{
low = mid+1;
}
}
return -1;
}
文章标题：leedcode每日一题：34. 在排序数组中查找元素的第一个和最后一个位置
文章链接：http://soscw.com/index.php/essay/63793.html