Leetcode 在排序数组中查找元素的第一个和最后一个位置
这段代码的目的是在一个有序的数组中查找目标元素的第一个和最后一个位置。如果目标元素不存在，返回 [-1, -1]。算法要求时间复杂度为 O(log n)，所以使用了二分查找的思想。
主要思路：
-
使用两次二分查找：
- 第一次二分查找用于找到目标元素的第一个位置。
- 第二次二分查找用于找到目标元素的最后一个位置。
-
在二分查找的过程中，通过调整搜索范围（即移动
start和end指针），分别定位目标元素的首次和末次出现的位置。
代码解析：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = {-1, -1}; // 初始化结果数组，默认值为 [-1, -1]
result[0] = findFirst(nums, target); // 找到目标的第一个位置
result[1] = findLast(nums, target); // 找到目标的最后一个位置
return result; // 返回结果
}
// 二分查找找到第一个出现的位置
private int findFirst(int[] nums, int target) {
int index = -1; // 初始化index为 -1，如果找不到目标元素，返回 -1
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2; // 计算中间位置，避免整数溢出
if (nums[mid] >= target) { // 如果中间元素大于或等于目标，缩小范围到左半部分
end = mid - 1;
} else { // 如果中间元素小于目标，缩小范围到右半部分
start = mid + 1;
}
if (nums[mid] == target) { // 当找到目标元素时，记录下当前位置
index = mid;
}
}
return index; // 返回找到的第一个位置，如果没找到，返回 -1
}
// 二分查找找到最后一个出现的位置
private int findLast(int[] nums, int target) {
int index = -1; // 初始化index为 -1，如果找不到目标元素，返回 -1
int start = 0, end = nums.length - 1;
while (start <= end) {
int mid = start + (end - start) / 2; // 计算中间位置
if (nums[mid] <= target) { // 如果中间元素小于或等于目标，缩小范围到右半部分
start = mid + 1;
} else { // 如果中间元素大于目标，缩小范围到左半部分
end = mid - 1;
}
if (nums[mid] == target) { // 当找到目标元素时，记录下当前位置
index = mid;
}
}
return index; // 返回找到的最后一个位置，如果没找到，返回 -1
}
}
算法思想：
-
二分查找的思想：
- 在一个有序数组中查找目标值，二分查找可以通过每次将搜索范围减半，从而达到 O(log n) 的时间复杂度。
- 这里我们分别实现了两次二分查找：
- 第一次查找目标值的第一个位置：每次找到目标值后，继续向左搜索，直到找到第一个出现的位置。
- 第二次查找目标值的最后一个位置：每次找到目标值后，继续向右搜索，直到找到最后一个出现的位置。
-
边界控制：
- 每次查找到目标值时，并不立即停止，而是继续缩小搜索范围以确保找到第一个或最后一个出现的目标值。
- 如果数组中不存在目标值，两个函数会返回默认的
-1，表示没有找到目标值。
时间复杂度：
- 每次二分查找的时间复杂度是 O(log n)，因为在每次循环中，我们将搜索范围缩小了一半。
- 两次二分查找的总时间复杂度是 O(2 * log n) ≈ O(log n)。
通过这种方法，我们能够在高效的时间内找到目标值的第一个和最后一个位置。
算法核心要点
算法中确实有两个核心要点：
1. nums[mid] 和 target 的大小判断使用的是大于等于 (>=) 或小于等于 (<=)：
- 在
findFirst方法中，使用>=确保当找到目标值后，继续向左查找以找到目标值的最左位置。即便找到了目标值，也不会立即停止搜索，而是继续检查是否存在更左边的目标值。 - 在
findLast方法中，使用<=确保当找到目标值后，继续向右查找以找到目标值的最右位置。同样地，即便找到了目标值，也不会立即返回，而是继续搜索右边，确保找到了最右边的目标值。
2. if (nums[mid] == target) 会多次更新 index：
- 当
nums[mid] == target时，我们会更新index，但不会立即返回index，而是继续调整搜索范围，查找目标值的更左或更右边界。 - 在
findFirst中，index可能会多次被更新，直到找到最左边的目标值位置。 - 在
findLast中，index同样会多次被更新，直到找到最右边的目标值位置。
总结：
- 大于等于/小于等于的判断：确保查找过程中不会错过目标值的边界（最左或最右位置）。
- 多次更新
index：在找到目标值时，并不会立即返回，而是继续更新，以确保最终返回的index是符合要求的最左或最右位置。
这两个核心点共同确保了算法能够高效地找到数组中目标值的第一个和最后一个位置，并且时间复杂度为 O(log n)。
原文地址：https://blog.csdn.net/coldasice342/article/details/142884308
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！