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

题目链接

leetcode

题目描述

给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
设计并实现时间复杂度为 O(log n) 的算法解决此问题。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

/*
    两次二分

    第一次二分：
        查找第一个位置，使得它的值大于等于 target，
    第二次二分：
        查找最后一个位置，使得它的值小于等于 target。
    注意：特判边界。

    时间复杂度：O(logn)
        其中 n 为数组的长度。
        二分查找的时间复杂度为 O(logn)，执行两次。
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = leftBound(nums, target);
        if (left == -1) {
            return {-1, -1};  // 如果未找到目标值，直接返回 [-1, -1]
        }

        int right = rightBound(nums, target);
        return {left, right};
    }

    int leftBound(const 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) {
                left = mid + 1;  // 区间变为 [mid+1, right]
            } else if (nums[mid] > target) {
                right = mid - 1; // 区间变为 [left, mid-1]
            } else if (nums[mid] == target) {
                right = mid - 1; // 收缩右侧边界
            }
        }
        // 检查 left 是否越界
        if (left >= nums.size() || nums[left] != target) {
            return -1;
        }

        return left;
    }

    int rightBound(const 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) {
                left = mid + 1;  // 区间变为 [mid+1, right]
            } else if (nums[mid] > target) {
                right = mid - 1; // 区间变为 [left, mid-1]
            } else if (nums[mid] == target) {
                left = mid + 1;  // 收缩左侧边界
            }
        }
        // 检查 right 是否越界
        if (right < 0 || nums[right] != target) {
            return -1;
        }

        return right;
    }
};

/*
    思路同上，寻找 target 在数组里的左右边界
*/
class Solution_1 {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lowerBound(nums, target);
        if (left == nums.size() || nums[left] != target) {
            return {-1, -1};  // 如果未找到目标值，直接返回 [-1, -1]
        }

        int right = lowerBound(nums, target+1)-1;
        return {left, right};
    }

    int lowerBound(const 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) {
                left = mid + 1;
            } else if (nums[mid] >= target) {
                right = mid - 1;
            }
        }

        // 循环结束后 left = right+1
        // 此时，nums[left-1] < target 并且 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {5,7,7,8,8,10},
        {5,7,7,8,8,10},
        {}
    };
    vector<int> target_cases = {
        8, 6, 0
    };

    for (size_t i = 0; i < nums_cases.size(); i++) {
        auto& nums = nums_cases[i];
        int target = target_cases[i];
        
        cout << "Input: nums = ";
        printArray(nums);
        cout << ", target = " << target << endl;
        vector<int> result = solution.searchRange(nums, target);
        cout << "Output: ";
        printArray(result);
        cout << endl;
    }

    return 0;
}