34. Find First and Last Position of Element in Sorted Array

Intuition

Since the array is sorted, we can use binary search to find:

1. The first occurrence of the target.

2. The last occurrence of the target.

Instead of expanding linearly after finding the target (which can take O(n) in worst case), we can use two separate binary search calls to maintain the required O(log n) time complexity.

Complexity

Space Complexity	Time Complexity
$\text{O}(1)$	$\text{O}(\log{N})$

Code

// Binary search to find the first (leftmost) occurrence
private int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length - 1, first = -1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        if (nums[mid] == target) {
            first = mid;         // potential answer found
            right = mid - 1;     // keep looking on the left
        } else if (nums[mid] < target) {
            left = mid + 1;      // move right
        } else {
            right = mid - 1;     // move left
        }
    }

    return first;
}

// Binary search to find the last (rightmost) occurrence
private int findLast(int[] nums, int target) {
    int left = 0, right = nums.length - 1, last = -1;

    while (left <= right) {
        int mid = (left + right) >> 1;

        if (nums[mid] == target) {
            last = mid;         // potential answer found
            left = mid + 1;     // keep looking on the right
        } else if (nums[mid] < target) {
            left = mid + 1;     // move right
        } else {
            right = mid - 1;    // move left
        }
    }

    return last;
}

// Main function
public int[] searchRange(int[] nums, int target) {
    int firstIndex = findFirst(nums, target);
    int lastIndex = findLast(nums, target);
    return new int[]{firstIndex, lastIndex};
}