二分查找有序重复元素
problem
给定一个按照升序排列的整数数组 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]
think
这题是让在升序数组中找到目标值，所以最容易想到的就是二分法查找，但这里数组中是有重复的元素，如果找到的是重复的就要返回重复元素的第一个和最后一个的位置，那么找到后分别往前和往后继续查找然后再比较key值。
在这里插入图片描述
code
class Solution {
public int[] searchRange(int[] nums, int target) {
int find = searchRangeHelper(nums, target);
//如果没找到，返回{-1, -1}
if (find == -1)
return new int[]{-1, -1};
int left = find - 1;
int right = find + 1;
//查看前面是否还有target
while (left >= 0 && nums[left] == target)
left--;
//查看后面是否还有target
while (right < nums.length && nums[right] == target)
right++;
return new int[]{left + 1, right - 1};
}
//二分法查找
private int searchRangeHelper(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = nums[mid];
if (midVal < target) {
low = mid + 1;
} else if (midVal > target) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
}复杂度分析：
时间复杂度：O(logN)，这里 N 是数组的长度 空间复杂度：O(1)，只使用了常数个数的辅助变量
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-02-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录