面试经典150题 P34 在排序数组中查找元素的第一个和最后一个位置

---

时间轴

时间轴

2025-12-04

init

分治

---

题目：

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

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

核心思路
我们在搜索过程中 不断缩小搜索区间。

• 当 nums[mid] >= target 时：target 可能在 mid 左边，所以把 right = mid - 1。
• 当 nums[mid] < target 时：target 在 mid 右边，所以 left = mid + 1。
• 每次遇到 nums[mid] == target 就记录 index = mid。

当循环结束时，left 超过了 right。最后记录的 index 一定是 满足 nums[index] == target 的最左位置：因为每次遇到 target 时，我们仍然尝试向左缩小区间（right = mid - 1）

#include <vector>
using std::vector;

class Solution {
    public:
        vector<int> searchRange(vector<int> &nums, int target)
        {
                int n = nums.size();
                int left = 0, right = n - 1;
                int mid;

                vector<int> res;
                int index = -1;
                while (left <= right) { //查找左边界
                        mid = left + (right - left) / 2;
                        if (nums[mid] >= target) {
                                right = mid - 1;
                        } else {
                                left = mid + 1;
                        }
                        if (nums[mid] == target)
                                index = mid;
                }

                res.push_back(index);

                left = 0;
                right = n - 1;
                index = -1;
                while (left <= right) { // 右边界
                        mid = left + (right - left) / 2;
                        if (nums[mid] <= target) {
                                left = mid + 1;
                        } else {
                                right = mid - 1;
                        }
                        if (nums[mid] == target)
                                index = mid;
                }
                res.push_back(index);

                return res;
        }
};

leetcode hot 100 rewrite:

#include <vector>

using std::vector;

class Solution {
    private:
        int search_range_end(vector<int> &nums, int target)
        {
                int n = nums.size();
                int left = 0, right = n - 1, mid;
                while (left < right) {
                        mid = left + (right - left + 1) / 2;
                        if (nums[mid] <= target)
                                left = mid;
                        else
                                right = mid - 1;
                }

                return (nums[left] == target) ? left : -1;
        }
        int search_range_start(vector<int> &nums, int target)
        {
                int n = nums.size();
                int left = 0, right = n - 1, mid;
                while (left < right) {
                        mid = left + (right - left) / 2;
                        if (nums[mid] >= target)
                                right = mid;
                        else
                                left = mid + 1;
                }

                return (nums[left] == target) ? left : -1;
        }

    public:
        vector<int> searchRange(vector<int> &nums, int target)
        {
                if (nums.empty())
                        return { -1, -1 };

                vector<int> res(2);
                res[0] = search_range_start(nums, target);
                res[1] = search_range_end(nums, target);
                return res;
        }
};