Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, 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]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Example 3:

Input: nums = [], target = 0 Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Approach: Two Binary Searches (Leftmost and Rightmost)

Algorithm

1. Use one binary search to find the first occurrence of target
2. Use another binary search to find the last occurrence of target
3. If the target is not found, return [-1, -1]
4. Otherwise return [first, last]

Time & Space Complexity

• Time Complexity: O(log n) - two binary searches
• Space Complexity: O(1) - iterative binary search

Java Implementation

public class FindFirstAndLastPositionOfElementInSortedArray {

    /**
     * Find the first and last position of target in a sorted array.
     * @param nums Sorted (non-decreasing) array
     * @param target Value to find
     * @return [firstIndex, lastIndex] or [-1, -1]
     */
    public static int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        if (first == -1) {
            return new int[]{-1, -1};
        }

        int last = findLast(nums, target);
        return new int[]{first, last};
    }

    private static int findFirst(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        int result = -1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                result = mid;
                hi = mid - 1; // keep searching to the left
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return result;
    }

    private static int findLast(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        int result = -1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                result = mid;
                lo = mid + 1; // keep searching to the right
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return result;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {5, 7, 7, 8, 8, 10};
        System.out.println("Input: nums = [5,7,7,8,8,10], target = 8");
        System.out.println("Output: " + java.util.Arrays.toString(searchRange(nums1, 8)));
        // Expected: [3, 4]

        int[] nums2 = {5, 7, 7, 8, 8, 10};
        System.out.println("Input: nums = [5,7,7,8,8,10], target = 6");
        System.out.println("Output: " + java.util.Arrays.toString(searchRange(nums2, 6)));
        // Expected: [-1, -1]

        int[] nums3 = {};
        System.out.println("Input: nums = [], target = 0");
        System.out.println("Output: " + java.util.Arrays.toString(searchRange(nums3, 0)));
        // Expected: [-1, -1]
    }
}

Example Walkthrough

For nums = [5,7,7,8,8,10], target = 8:

1. findFirst: binary search locates 8 at index 4; continue left -> 8 at index 3; continue left -> 7, stop. first = 3
2. findLast: binary search locates 8 at index 3; continue right -> 8 at index 4; continue right -> 10, stop. last = 4
3. Return [3, 4]

Key Points

1. Two Searches: The first occurrence and last occurrence require separate binary searches
2. Continue After Match: To find the first, keep searching left; to find the last, keep searching right
3. Not Found Handling: Early return [-1, -1] when the first search fails
4. O(log n): Both searches halve the range each step
5. Empty Array: The empty array case returns [-1, -1] naturally