Find First and Last Position of Element in Sorted Array medium

Problem Statement

Given a sorted array of integers nums and an integer target, find the indices of the first and last occurrences of target in nums. If target is not found, return [-1, -1].

Example 1

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] Explanation: The first occurrence of 8 is at index 3, and the last occurrence is at index 4.

Example 2

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1] Explanation: 6 is not present in the array.

Steps

The solution uses binary search twice:

1. Find the first occurrence: Perform binary search to find the leftmost index where target is present. If found, store the index. If not found, the first occurrence doesn't exist.
2. Find the last occurrence: Perform binary search to find the rightmost index where target is present. This is similar to step 1 but modified to find the rightmost occurrence. If found, store the index. If not found, the last occurrence doesn't exist.
3. Return the result: Return the indices found in steps 1 and 2. If either the first or last occurrence was not found, return [-1, -1].

Explanation

The core idea is to efficiently locate the boundaries of the target element within the sorted array using binary search. A standard binary search only finds one occurrence. To find both the first and last, we need to adapt the binary search algorithm slightly.

When searching for the first occurrence, we prioritize searching in the left half if the middle element is equal to the target (since there might be earlier occurrences). Conversely, when searching for the last occurrence, we prioritize the right half. This guarantees we find the extreme boundaries.

Code

#include <vector>

using namespace std;

vector<int> searchRange(vector<int>& nums, int target) {
    int first = -1, last = -1;

    // Find first occurrence
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            first = mid;
            right = mid - 1; // Continue searching in the left half
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // Find last occurrence
    left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            last = mid;
            left = mid + 1; // Continue searching in the right half
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return {first, last};
}

Complexity

• Time Complexity: O(log n), where n is the length of the input array. This is because we perform binary search twice.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.