Code Implementation

class Solution:
    def searchRange(self, nums, target):
        def findLeft(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left

        def findRight(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right

        left_idx = findLeft(nums, target)
        right_idx = findRight(nums, target)
        if left_idx <= right_idx and left_idx < len(nums) and nums[left_idx] == target and nums[right_idx] == target:
            return [left_idx, right_idx]
        else:
            return [-1, -1]
      

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = findLeft(nums, target);
        int right = findRight(nums, target);
        if (left <= right && left < nums.length && right >= 0 && nums[left] == target && nums[right] == target)
            return new int[]{left, right};
        return new int[]{-1, -1};
    }
    
    private int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
    
    private int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return right;
    }
}
      

var searchRange = function(nums, target) {
    function findLeft(nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    function findRight(nums, target) {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
    
    let leftIdx = findLeft(nums, target);
    let rightIdx = findRight(nums, target);
    if (leftIdx <= rightIdx && leftIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) {
        return [leftIdx, rightIdx];
    } else {
        return [-1, -1];
    }
};
      

Problem Description

Given a sorted array of integers nums and a target value target, you are asked to find the starting and ending positions of target in nums. If target is not present in the array, you should return [-1, -1].

The problem emphasizes efficiency: your solution must have a runtime complexity of O(log n), taking advantage of the fact that nums is sorted in non-decreasing order. The output should be a pair of indices: the first and last occurrence of target.

• If target is not found, return [-1, -1].
• All elements in nums are integers, and nums may be empty.
• The solution should not "reuse" elements; you are to find indices, not values.

Thought Process

At first glance, you might consider scanning through nums from start to finish, marking the first and last time you see target. This brute-force approach works but is inefficient for large arrays because it checks every element, resulting in O(n) time complexity.

However, since nums is sorted, we can do better. Binary search is ideal for sorted arrays, allowing us to quickly "zoom in" on the area where target appears. The challenge is not just to find if target exists, but to find its first and last positions. This requires a modified binary search: one to find the leftmost (first) index, and one to find the rightmost (last) index.

By splitting the problem into two searches (left and right bounds), we can maintain O(log n) efficiency and avoid unnecessary scanning.

Solution Approach

The optimized solution leverages binary search to efficiently find the first and last positions of target in nums.

1. Find the First Occurrence:
   • Use binary search to look for target.
   • If nums[mid] is less than target, move the left boundary up.
   • If nums[mid] is greater than or equal to target, move the right boundary down.
   • This ensures that when the loop ends, left points to the first occurrence of target (or where it would be).
2. Find the Last Occurrence:
   • Similar to the first search, but adjust the binary search condition.
   • If nums[mid] is less than or equal to target, move the left boundary up.
   • If nums[mid] is greater than target, move the right boundary down.
   • This ensures that when the loop ends, right points to the last occurrence of target (or where it would be).
3. Check for Validity:
   • After both searches, confirm that the found indices are within bounds and actually point to target.
   • If not, return [-1, -1].
   • Otherwise, return the found indices.

This approach ensures we only use O(log n) time by never scanning more than necessary.

Example Walkthrough

Let's walk through an example with nums = [5,7,7,8,8,10] and target = 8.

1. Find the First Occurrence:
   • Start: left = 0, right = 5
   • mid = 2, nums[2]=7 < 8, so left = 3
   • mid = 4, nums[4]=8 == 8, so right = 3
   • mid = 3, nums[3]=8 == 8, so right = 2
   • Loop ends: left = 3
2. Find the Last Occurrence:
   • Start: left = 0, right = 5
   • mid = 2, nums[2]=7 <= 8, so left = 3
   • mid = 4, nums[4]=8 <= 8, so left = 5
   • mid = 5, nums[5]=10 > 8, so right = 4
   • Loop ends: right = 4
3. Check Validity:
   • left = 3, right = 4
   • nums[3]=8, nums[4]=8, so return [3, 4]

If target = 6, both searches would find no valid index, so the result would be [-1, -1].

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n), since you may have to scan the entire array.
  • Space Complexity: O(1), as only a few variables are needed.
• Optimized (binary search) approach:
  • Time Complexity: O(log n), because each binary search halves the search space.
  • Space Complexity: O(1), as the search uses only a fixed number of variables.

The optimized approach is significantly faster for large arrays, making full use of the array's sorted property.

Summary

This problem demonstrates the power of binary search for sorted arrays. By carefully adjusting the search conditions, we can efficiently find both the first and last occurrences of a target value in O(log n) time. The key insight is to treat the two searches (left and right bounds) separately, ensuring precision and efficiency. This approach is elegant, concise, and leverages fundamental algorithmic strategies every programmer should know.