Problem Statement

Given an array of integers sorted in non-decreasing order, identify the starting and ending index of a specified target value. If the target is absent from the array, return [-1, -1]. The solution must operate with a logarithmic time complexity of O(log n).

Expected Outcomes

• For data = [5, 7, 7, 8, 8, 10], target = 8, the output should be [3, 4].
• For data = [5, 7, 7, 8, 8, 10], target = 6, the output should be [-1, -1].
• For data = [], target = 0, the output should be [-1, -1].

Algorithm Strategy

A standard linear scan would result in O(n) time complexity, which violates the problem constraints. To achieve O(log n), binary search is required. Since we need both the first and last occurrence, we can execute two separate binary searches:

1. Left Boundary Search: When the target is found, record the index and continue searching the left half to find an earlier occurrence.
2. Right Boundary Search: When the target is found, record the index and continue searching the right half to find a later occurrence.

Implementation

The two searches can be consolidated into a single helper method that accepts a boolean flag to determine the search direction upon finding a match.

import java.util.Arrays;

public class BoundaryFinder {

    public static int[] findRange(int[] data, int key) {
        int firstPos = searchBoundary(data, key, true);
        int lastPos = searchBoundary(data, key, false);
        return new int[]{firstPos, lastPos};
    }

    private static int searchBoundary(int[] data, int key, boolean findFirst) {
        int low = 0;
        int high = data.length - 1;
        int result = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // Prevents potential integer overflow

            if (key > data[mid]) {
                low = mid + 1;
            } else if (key < data[mid]) {
                high = mid - 1;
            } else {
                result = mid; // Mark the found position
                if (findFirst) {
                    // Keep looking towards the left
                    high = mid - 1;
                } else {
                    // Keep looking towards the right
                    low = mid + 1;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(findRange(arr1, 8))); // Output: [3, 4]

        int[] arr2 = {5, 7, 7, 8, 8, 10};
        System.out.println(Arrays.toString(findRange(arr2, 6))); // Output: [-1, -1]

        int[] arr3 = {};
        System.out.println(Arrays.toString(findRange(arr3, 0))); // Output: [-1, -1]
    }
}