Interview Classic 150 Questions P34 Find First and Last Position of Element in Sorted Array

---

Timeline

timeline

2025-12-04

init

divide and conquer

---

Title:

P34 Find First and Last Position of Element in Sorted Array

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

Core Idea
During the search, we continuously narrow down the search interval.

• When nums[mid] >= target: target may be to the left of mid, so set right = mid - 1.
• When nums[mid] < target: target is to the right of mid, so set left = mid + 1.
• Each time nums[mid] == target, record index = mid.

When the loop ends, left exceeds right. The last recorded index must be the leftmost position where nums[index] == target: because each time we encounter target, we still try to narrow the interval to the left (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) { //Find Left Boundary
                        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) { // right boundary
                        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;
        }
};