34. 在排序数组中查找元素的第一个和最后一个位置

题目

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

函数执行过程

1. 初始化：

   • left = 0
   • right = 4 (数组的最后一个索引)
   • ans = 5 (数组大小)

2. 第一次循环：

   • mid = (0 + 4) / 2 = 2，nums[mid] = 4
   • nums[mid] > target，即 4 > 3，所以：
     • right = mid - 1 = 1
     • ans = mid = 2

3. 第二次循环：

   • left = 0，right = 1
   • mid = (0 + 1) / 2 = 0，nums[mid] = 1
   • nums[mid] <= target，所以：
     • left = mid + 1 = 1

4. 第三次循环：

   • left = 1，right = 1
   • mid = (1 + 1) / 2 = 1，nums[mid] = 2
   • nums[mid] <= target，所以：
     • left = mid + 1 = 2

5. 退出循环：

   • 现在 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的值为距离查找值最近的那个索引。