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 in nums, 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] Explanation: The first occurrence of 8 is at index 3 and the last is at index 4.

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 utilizes binary search twice: once to find the leftmost occurrence and once to find the rightmost occurrence of the target.

1. Find Leftmost Occurrence:

   • Perform binary search on the input array.
   • If the target is found at mid, check if it's the leftmost occurrence by checking nums[mid - 1]. If nums[mid - 1] is equal to the target, continue searching in the left half. Otherwise, this is the leftmost occurrence.
   • If the target is not found, return -1 (for both left and right).

2. Find Rightmost Occurrence:

   • Perform a similar binary search.
   • If the target is found at mid, check if it's the rightmost occurrence by checking nums[mid + 1]. If nums[mid + 1] is equal to the target, continue searching in the right half. Otherwise, this is the rightmost occurrence.
   • If the target is not found, the previous result (-1) is still valid.

Explanation

The efficiency comes from using binary search. Binary search has a time complexity of O(log n), so performing it twice still maintains the O(log n) runtime. This is significantly better than a linear scan (O(n)). The key is the logic within the binary search to ensure we find the extremes (leftmost and rightmost) of the target occurrences.

Code

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int left = FindLeftmost(nums, target);
        int right = FindRightmost(nums, target);
        return new int[] { left, right };
    }

    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 on the left
            } 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 on the right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }
}

Complexity

• Time Complexity: O(log n) - Due to the two binary searches.
• Space Complexity: O(1) - Constant extra space is used. The space used is independent of the input size.