leetcode刷题（89）——34. 在排序数组中查找元素的第一个和最后一个位置
leetcode刷题（89）——34. 在排序数组中查找元素的第一个和最后一个位置
老马的编程之旅
发布于 2022-06-22 13:57:14
发布于 2022-06-22 13:57:14
文章被收录于专栏：深入理解Android
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]其实这里就是二分查找的变体，思路就是分别求左右界，然后进行合并即可，代码如下
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftRange = findLeftRange(nums,target);
int rightRange = findRightRange(nums,target);
return new int[]{leftRange,rightRange};
}
private int findLeftRange(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left<=right){
int middle = left + (right - left)/2;
int middleValue = nums[middle];
if(middleValue<target){
left = middle+1;
}else if(middleValue>target){
right = middle-1;
}else if(middleValue == target){
right = middle-1;
}
}
if(left>=nums.length||left<0){
return -1;
}
if(nums[left]==target){
return left;
}
return -1;
}
private int findRightRange(int[] nums, int target){
int left = 0;
int right = nums.length - 1;
while(left<=right){
int middle = left + (right - left)/2;
int middleValue = nums[middle];
if(middleValue<target){
left = middle+1;
}else if(middleValue>target){
right = middle-1;
}else if(middleValue == target){
left = middle+1;
}
}
if(right<0||right>=nums.length){
return -1;
}
if(nums[right]==target){
return right;
}
return -1;
}
}唯一需要注意的是，当middleValue == target时不是立即返回而是缩短边界继续搜索，就拿findRightRange来说
else if(middleValue == target){
left = middle+1;
}需要注意这里使用的是middle+1，因为我们判断while循环时候是while(left<=right)，所以middle值是已经被检索过了，不要多次检索，否则会一直在循环中出不来，如果是while(left<right)，则left = middle;
其次要注意边界处理的情况
if(right<0||right>=nums.length){
return -1;
}
if(nums[right]==target){
return right;
}
return -1;本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
