First and Last position of an element in a sorted array

Problem Link

find-first-and-last-position-of-element-in-sorted-array

Problem Statement

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

If the target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Examples:

• Input: nums = [5,7,7,8,8,10], target = 8
  Output: [3, 4]

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

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

Constraints:

• 0 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

• nums is sorted in non-decreasing order

• -10^9 <= target <= 10^9

Intuition

The array is sorted, and we need to find both the first and last occurrence of the target. A simple linear search would be O(n), which violates the time complexity requirement.

Since we are working with a sorted array and aiming for O(log n), binary search must be used. However, standard binary search only finds a single occurrence. To solve this, we modify binary search to find:

• The first occurrence by always moving left even after a match.

• The last occurrence by always moving right even after a match.

Approach

1. Create a helper method find that performs a binary search.

2. Pass a flag isFirst to determine whether to look for the first or last occurrence.

3. In the find method:

   • If a match is found, store the index in potAns (potential answer).

   • Continue searching:

     • If isFirst is true, search the left half (end = mid - 1).

     • Else, search the right half (start = mid + 1).

4. In the main method:

   • Call find with isFirst = true for the first position.

   • If found, call find again with isFirst = false for the last position.

   • If not found, return [-1, -1].

Code in Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = find(nums, target, true);
        if (first != -1) {
            int second = find(nums, target, false);
            return new int[]{first, second};
        }
        return new int[]{-1, -1};
    }

    private int find(int[] nums, int target, boolean isFirst) {
        int start = 0;
        int end = nums.length - 1;
        int potAns = -1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                potAns = mid;
                if (isFirst) {
                    end = mid - 1; // keep searching left
                } else {
                    start = mid + 1; // keep searching right
                }
            } else if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return potAns;
    }
}

Time and Space Complexity

• Time Complexity:
  O(log n) for finding the first occurrence + O(log n) for finding the last occurrence = O(log n) total.

• Space Complexity:
  O(1) — constant space is used.

Dry Run

Input:

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

First Call (isFirst = true):

• start = 0, end = 5, mid = 2 → nums[2] = 7 < 8 → start = 3

• mid = 4, nums[4] = 8 → match → store potAns = 4, end = 3

• mid = 3, nums[3] = 8 → match → update potAns = 3, end = 2

• Loop ends → first = 3

Second Call (isFirst = false):

• start = 0, end = 5, mid = 2 → nums[2] = 7 < 8 → start = 3

• mid = 4, nums[4] = 8 → match → store potAns = 4, start = 5

• mid = 5, nums[5] = 10 > 8 → end = 4

• Loop ends → last = 4

Output: [3, 4]

Conclusion

This problem demonstrates how to extend binary search to find boundary positions (first and last occurrences) of a target in a sorted array. The key is to modify the search direction even after finding the target to ensure we locate the extreme ends.

Using this dual binary search pattern is efficient and scalable for large arrays, satisfying the O(log n) constraint.