Example: Search for a Range - rFronteddu/general_wiki GitHub Wiki

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.

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }
        
        int left = 0;
        int right = nums.length - 1;

        int targetIndex = -1;
        
        // find target
        while (left <= right) {
            // Prevent (left + right) overflow
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                targetIndex = mid;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1; // Adjust left pointer
            } else {
                right = mid - 1; // Adjust right pointer
            }
        }
        if (targetIndex == -1) {
            return new int[]{-1, -1};
        }

        // find smaller left index
        int smallerLeft = -1;
        left = 0;
        right = targetIndex;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                smallerLeft = mid;
                right = mid - 1; // Adjust right pointer
            } else if (nums[mid] < target) {
                left = mid + 1; // Adjust left pointer
            } else {
                right = mid - 1; // Adjust right pointer
            }
        }
        if(smallerLeft == -1) smallerLeft = targetIndex;
        
        // find bigger right index
        int biggerRight = -1;
        left = targetIndex;
        right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                biggerRight = mid;
                left = mid + 1; // Adjust right pointer
            } else if (nums[mid] < target) {
                left = mid + 1; // Adjust left pointer
            } else {
                right = mid - 1; // Adjust right pointer
            }
        }
        if(biggerRight == -1) biggerRight = targetIndex;
    
        return new int[]{smallerLeft, biggerRight};
    }
}