目录
- 题目
- 解法
- 如果找不到目标值,会返回什么结果?
- 函数解释
- 具体例子
- 函数执行过程
- 返回结果
- 总结
题目
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
解法
class Solution {
public:int binarySearch(vector<int>& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return vector<int>{leftIdx, rightIdx};} return vector<int>{-1, -1};}
};
如果找不到目标值,会返回什么结果?
让我们通过一个具体的例子来展示在使用你提供的 binarySearch
函数时,如果找不到目标值 target
,返回的 ans
会是什么结果。
函数解释
这个 binarySearch
函数用于在一个已排序的数组 nums
中查找目标值 target
。它有一个额外的布尔参数 lower
,这个参数用于区分查找目标值的下界(如果为 true
)或上界(如果为 false
)。如果目标值不存在,函数将返回 ans
,这个值初始化为 nums.size()
,表示没有找到目标值。
具体例子
假设我们有如下数组和目标值:
vector<int> nums = {1, 2, 4, 5, 6};
int target = 3;
bool lower = true; // 或 false,这里我们可以先设为 true
函数执行过程
-
初始化:
left = 0
right = 4
(数组的最后一个索引)ans = 5
(数组大小)
-
第一次循环:
mid = (0 + 4) / 2 = 2
,nums[mid] = 4
nums[mid] > target
,即4 > 3
,所以:right = mid - 1 = 1
ans = mid = 2
-
第二次循环:
left = 0
,right = 1
mid = (0 + 1) / 2 = 0
,nums[mid] = 1
nums[mid] <= target
,所以:left = mid + 1 = 1
-
第三次循环:
left = 1
,right = 1
mid = (1 + 1) / 2 = 1
,nums[mid] = 2
nums[mid] <= target
,所以:left = mid + 1 = 2
-
退出循环:
- 现在
left = 2
,right = 1
,条件left <= right
不再满足,退出循环。
- 现在
返回结果
在整个过程中,ans
的值变为 2
,这是 target
3 应该插入的位置,以保持数组的有序性。因为在数组中没有 3
,所以 ans
返回的值实际上是 3
应该插入的位置。
因此,如果调用 binarySearch(nums, target, lower)
,在找不到目标值的情况下返回的结果为:
int result = binarySearch(nums, target, true); // result 为 2
总结
- 如果在数组中找不到目标值
target
,ans
会返回目标值应插入的索引位置,以保持数组的有序性。 - 在上述例子中,返回的
ans
值为2
,表示3
应该插入到索引2
的位置。
找不到的话会退出循环,然后ans的值为距离查找值最近的那个索引。