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 starting and ending positions 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 position of 8 is at index 3 (nums[3] = 8) and the last position of 8 is at index 4 (nums[4] = 8).

Example 2

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

Steps

The solution leverages binary search twice: once to find the leftmost occurrence and once to find the rightmost occurrence of the target.

1. Find Leftmost Occurrence: Perform a binary search modified to prioritize finding the leftmost occurrence. If a target is found, continue searching in the left half.

2. Find Rightmost Occurrence: Perform another binary search, this time modified to prioritize finding the rightmost occurrence. If a target is found, continue searching in the right half.

3. Return Result: Return an array containing the indices of the leftmost and rightmost occurrences. If the target is not found in either search, return [-1, -1].

Explanation

The key to efficiency here is the modification of the standard binary search. A standard binary search stops as soon as it finds a target. We need to adapt it to keep searching to the left (for the leftmost) or right (for the rightmost) even after finding a target.

For instance, when searching for the leftmost occurrence and the mid element matches the target, we don't stop. We continue to check the left subarray because there might be an earlier occurrence of the target. The opposite applies for finding the rightmost occurrence.

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};

        // Find leftmost occurrence
        int left = findLeftmost(nums, target);
        result[0] = left;

        // Find rightmost occurrence
        int right = findRightmost(nums, target);
        result[1] = right;

        return result;
    }

    private int findLeftmost(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                right = mid - 1; // Continue searching in the left half
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    private int findRightmost(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result = mid;
                left = mid + 1; // Continue searching in the right half
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

Complexity

• Time Complexity: O(log n). Binary search is used twice, each with a logarithmic time complexity.
• Space Complexity: O(1). The solution uses a constant amount of extra space.