문제

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.

제한사항

• 0 <= nums.length <= $10^5$
• $-10^9$ <= nums[i] <= $-10^9$
• nums is a non-decreasing array.
• $-10^9$ <= target <= $10^9$

접근

이번 문제도 이분탐색 응용 문제였어요.

1. 이분탐색을 통해 target을 찾아요.
   1-1. 최소 인덱스와 최대 인덱스를 찾는데, 처음에 1번의 인덱스를 각 최소, 최대 인덱스에 저장해야 정상 작동해요.
2. left = 0, right =target - 1 범위로 target을 이분탐색합니다.
3. left = target + 1, right = nums.length - 1 범위로 target을 이분탐색합니다.
4. 2, 3번 과정을 통해 얻은 값을 반환합니다.

답안

public int[] searchRange(int[] nums, int target) {
        int[] ret = new int[]{-1, -1};

        int firstIndex = Arrays.binarySearch(nums, target);
        if(firstIndex < 0)
            return ret;

        // 최소 인덱스 찾기
        int minIndex = firstIndex;
        int left = 0, right = firstIndex - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;

            if(nums[mid] < target) {
                left = mid + 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            }
            else{
                minIndex = mid;
                right = mid - 1;
            }
        }
        ret[0] = minIndex;

        // 최대 인덱스 찾기
        int maxIndex = firstIndex;
        left = firstIndex + 1;
        right = nums.length - 1;
        while(left <= right){
            int mid = (left + right) >>> 1;

            if(nums[mid] < target) {
                left = mid + 1;
            } else if(target < nums[mid]) {
                right = mid - 1;
            }
            else{
                maxIndex = mid;
                left = mid + 1;
            }
        }
        ret[1] = maxIndex;
        
        return ret;
    }