网站改版对优化的影响相亲小程序源码
原题链接🔗：在排序数组中查找元素的第一个和最后一个位置
难度：中等⭐️⭐️
题目
给你一个按照非递减顺序排列的整数数组 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]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
二分查找
-
二分查找（Binary Search），也称为折半搜索，是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较：
- 如果目标值等于中间元素，搜索成功，返回该位置。
- 如果目标值小于中间元素，搜索范围缩小至数组的左半部分。
- 如果目标值大于中间元素，搜索范围缩小至数组的右半部分。
- 这个过程将不断重复，直到找到目标值或者搜索范围为空为止。
-
以下是二分查找算法的一般步骤：
-
初始化：设置两个指针，一个指向数组的起始位置（通常记为
left），另一个指向数组的结束位置（通常记为right）。 -
循环条件：当
left小于等于right时，继续循环。 -
计算中间位置：计算
left和right之间的中间位置mid，通常使用(left + right) / 2。 -
比较与调整：
- 如果
nums[mid]等于目标值，根据需要返回mid或继续搜索以找到更精确的位置。 - 如果
nums[mid]大于目标值，将right调整为mid - 1。 - 如果
nums[mid]小于目标值，将left调整为mid + 1。
- 如果
-
循环结束：如果
left大于right，则表示目标值不在数组中，返回一个特定的值（通常是 -1）表示未找到。
-
-
二分查找的效率非常高，时间复杂度为 O(log n)，其中 n 是数组的长度。然而，它要求数组是有序的，并且只能应用于一维有序数组。
-
下面是一个简单的 C++ 实现示例：
int binarySearch(const std::vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止溢出if (nums[mid] == target) {return mid; // 找到目标值} else if (nums[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid - 1; // 搜索左半部分}}return -1; // 未找到目标值
}
这个函数会返回目标值在数组中的索引，如果目标值不在数组中，则返回 -1。
题解
- 解题思路：
LeetCode 上的这个问题通常被称为“Find First and Last Position of Element in Sorted Array”，题目编号为 34。这个问题可以通过二分查找算法来解决，因为数组是已经排序的。
以下是解决这个问题的一般思路：
理解问题：首先，你需要理解问题的要求，即在一个升序排序的数组中找到给定元素的第一个和最后一个位置。
二分查找：由于数组是有序的，你可以使用二分查找来找到目标元素的索引。二分查找的基本思想是将数组分成两半，比较中间元素与目标值，然后根据比较结果决定是继续在左半部分查找还是右半部分查找。
找到第一个位置：使用二分查找，但需要稍作修改以找到第一个位置。在每次迭代中，如果中间元素等于目标值，你不能立即返回这个位置，因为可能还有更小的索引也是目标值。你需要向左半边继续查找。
找到最后一个位置：同样使用二分查找，但这次如果中间元素等于目标值，你需要向右半边继续查找，因为可能还有更大的索引也是目标值。
边界条件：在查找过程中，需要处理数组的边界条件，确保不会访问数组之外的索引。
- c++ demo：
#include <vector>
#include <iostream>// 二分查找函数，用于找到目标值的索引
int binarySearch(const std::vector<int>& nums, int target, bool findFirst) {int left = 0, right = nums.size() - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {result = mid; // 记录找到的位置if (findFirst) {right = mid - 1; // 向左查找第一个位置}else {left = mid + 1; // 向右查找最后一个位置}}else if (nums[mid] < target) {left = mid + 1;}else {right = mid - 1;}}return result;
}// 主函数，用于找到元素的第一个和最后一个位置
std::vector<int> findFirstAndLastPosition(const std::vector<int>& nums, int target) {int first = binarySearch(nums, target, true); // 找到第一个位置int last = binarySearch(nums, target, false); // 找到最后一个位置return { first, last };
}int main() {std::vector<int> nums = { 5, 7, 7, 8, 8, 10 };int target = 8;std::vector<int> positions = findFirstAndLastPosition(nums, target);std::cout << "First position: " << positions[0] << std::endl;std::cout << "Last position: " << positions[1] << std::endl;return 0;
}
- 输出结果：
First position: 3
Last position: 4
- 代码仓库地址：findFirstAndLastPosition