Find First and Last Position of Element in Sorted Array

Link

Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with \(O(\log n)\) runtime complexity.

Example 1:

• Input: nums = [5,7,7,8,8,10], target = 8
• Output: [3,4]

Example 2:

• Input: nums = [5,7,7,8,8,10], target = 6
• Output: [-1,-1]

Example 3:

• Input: nums = [], target = 0
• Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

Solution

Binary Search Template 1

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        // (NOTE!!!) We need to check if the array is empty
        if (nums.empty()) {
            return vector<int>{-1, -1};
        }
        int l = -1, r = nums.size();
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid;
        }

        // (NOTE!!!) Check if r is within bounds and if the target is found
        if (r >= nums.size() || nums[r] != target) {
            return vector<int>{-1, -1};
        } else {
            res.push_back(r);
            l = -1, r = nums.size();
            while (l + 1 < r) {
                int mid = l + (r - l) / 2;
                if (nums[mid] <= target) l = mid;
                else r = mid;
            }
            res.push_back(l);
        }
        return res;
    }
};

Another way of writing:

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

public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.size() || nums[start] != target) {
            return {-1, -1};
        }
        int end = lowerBound(nums, target + 1) - 1;
        return {start, end};
    }
};

Binary Search Template 2

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.empty()) {
            return vector<int>{-1, -1};
        }
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] != target) return {-1, -1};
        int left_res = r;

        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return {left_res, r};  //return {left_res, l}; is also OK
    }
};

Notes

1. Index of the first element greater than or equal to x: lower_bound(x)

This operation finds the position of the first element in a sorted array that is not less than (i.e., greater than or equal to) a specified value x.

Explanation: The lower_bound function in C++ returns an iterator pointing to the first element in the range [first, last) that is not less than x. If all elements are less than x, it returns an iterator to the end of the range.

C++ Code Example:

#include <algorithm> // For lower_bound
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 4, 4, 5, 7, 9};
    int x = 4;
    auto it = std::lower_bound(v.begin(), v.end(), x);
    int index = it - v.begin();
    std::cout << "Index of the first element >= " << x << ": " << index << std::endl;
    return 0;
}

2. Index of the first element greater than x: can be treated as the index of the first element greater than or equal to x+1, lower_bound(x+1)

Explanation: By searching for x+1, we effectively find the first element that is strictly greater than x.

C++ Code Example:

// Reusing the setup from the first example, just change x to x+1
int x = 4;
auto it = std::lower_bound(v.begin(), v.end(), x + 1);
int index = it - v.begin();
std::cout << "Index of the first element > " << x << ": " << index << std::endl;

3. Index of the last element less than x: can be treated as one position to the left of the index of the first element greater than or equal to x, lower_bound(x) - 1

Explanation: To find the last element that is less than x, we find the position of the first element that is greater than or equal to x and then subtract one.

C++ Code Example:

// Assume v and x are defined as before
auto it = std::lower_bound(v.begin(), v.end(), x);
int index = (it - v.begin()) - 1; // Subtracting 1 to get the index of the element just before it
std::cout << "Index of the last element < " << x << ": " << index << std::endl;

4. Index of the last element less than or equal to x: can be treated as one position to the left of the index of the first element greater than or equal to x+1, lower_bound(x+1) - 1

Explanation: This is similar to the previous case, but we are interested in the last element that is less than or equal to x. We achieve this by looking for x+1 and then stepping back one position.

C++ Code Example:

// Assume v and x are defined as before
auto it = std::lower_bound(v.begin(), v.end(), x + 1);
int index = (it - v.begin()) - 1; // Subtracting 1
std::cout << "Index of the last element <= " << x << ": " << index << std::endl;