一、题目
给你一个按照非递减顺序排列的整数数组 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