一、题目
给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target
,返回 [-1, -1]
。
你必须设计并实现时间复杂度为 O(log n)
的算法解决此问题。
二、解题思路
1. 查找起始位置:
- 使用二分查找确定目标值是否存在于数组中,并找到其第一次出现的位置。
- 如果目标值不存在,直接返回 [-1, -1]。
- 如果目标值存在,记录这个位置作为起始位置。
2. 查找结束位置:
- 由于数组是有序的,我们可以从起始位置开始,向右进行二分查找,但是这次我们寻找的是目标值最后一次出现的位置。
- 我们需要调整二分查找的逻辑,使其在找到目标值后继续向右查找,直到找不到目标值为止。
三、具体代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = -1, right = -1;
int len = nums.length;
// 查找起始位置
int mid = 0;
while (mid < len) {
if (nums[mid] == target) {
left = mid;
break;
} else if (nums[mid] < target) {
mid += (len - mid) / 2;
} else {
len = mid;
}
}
// 如果没有找到目标值,直接返回 [-1, -1]
if (left == -1) {
return new int[]{left, right};
}
// 查找结束位置
right = left;
len = nums.length;
while (right < len) {
int pos = right + (len - right) / 2;
if (nums[pos] == target) {
right = pos;
len = pos;
} else {
right = pos + 1;
}
}
return new int[]{left, right};
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 时间复杂度是 O(log n)。
- 查找起始位置的二分查找操作是 O(log n),因为每次迭代都将搜索范围减半。
- 查找结束位置的二分查找操作同样是 O(log n),原因同上。
- 两个二分查找操作是独立的,所以总的时间复杂度是 O(log n) + O(log n) = O(log n)。
2. 空间复杂度
- 空间复杂度是 O(1)。
- 代码中没有使用额外的数据结构来存储数据,所有的变量都是局部变量,其空间需求与输入数组的大小无关。
- 因此,空间复杂度是 O(1),即常数空间复杂度。
五、总结知识点
1. 二分查找(Binary Search):
- 二分查找是一种在有序数组中查找特定元素的高效算法。
- 它通过将目标值与数组中间元素进行比较,根据比较结果缩小搜索范围,直到找到目标值或搜索范围为空。
2. 循环结构:
- 使用
while
循环来实现二分查找的迭代过程。 - 循环条件和迭代逻辑是二分查找算法的核心部分。
3. 条件判断:
- 在二分查找过程中,使用
if-else
语句来判断数组中间元素与目标值的关系,从而决定是向左半部分还是向右半部分继续查找。
4. 变量初始化与更新:
- 初始化
left
和right
变量为 -1,表示目标值的起始和结束位置未找到。 - 在查找过程中,根据查找结果更新这些变量的值。
5. 数组操作:
- 使用数组索引来访问和比较数组中的元素。
6. 返回值:
- 返回一个包含两个整数的数组,分别表示目标值的起始和结束位置。
- 如果目标值不存在于数组中,则返回 [-1, -1]。
7. 边界条件处理:
- 在查找结束位置时,需要特别处理边界条件,确保不会访问数组的无效索引。
8. 算法效率:
- 代码实现了 O(log n) 的时间复杂度,这是二分查找算法的典型时间复杂度。
- 空间复杂度为 O(1),因为除了输入数组外,没有使用额外的空间。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
标签:二分,right,复杂度,查找,数组,目标值,排序,LeetCode From: https://blog.csdn.net/weixin_62860386/article/details/136427939