给你一个按照非递减顺序排列的整数数组 nums ,和一个目标值 target 。请你找出给定目标值在数组 中的开始位置和结束位置。 如果数组中不存在目标值 target ,返回 [-1, -1] 。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。用java
时间: 2024-09-15 13:13:42 浏览: 55
两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个
这个问题可以使用二分查找法(Binary Search)来解决,因为数组已经是非递减排序的。在Java中,你可以这样做:
```java
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[]{-1, -1};
}
int left = binarySearchLeft(nums, target);
if (left == -1) {
// 目标值不在数组中
return new int[]{-1, -1};
}
int right = binarySearchRight(nums, target, left);
if (right == -1) {
// 目标值只出现一次,在左边界
right = left;
} else {
// 目标值在数组中,找到右边界
}
return new int[]{left, right};
}
private int binarySearchLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return nums[left] == target ? left : -1;
}
private int binarySearchRight(int[] nums, int target, int start) {
int left = start + 1, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - 1;
} else {
left = mid + 1;
}
}
return nums[left] == target ? left : -1;
}
}
```
这里,`binarySearchLeft`函数用于查找第一个大于等于`target`的元素的位置,而`binarySearchRight`函数则从已知的目标值所在范围内的下一个元素开始查找,寻找第一个大于`target`的元素。如果找到了这样的元素,那么`right`就是目标值的右边界。
阅读全文