[LeetCode] Find First and Last Position of Element in Sorted Array (Java)

leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Find First and Last Position of Element in Sorted Array - LeetCode

 

 

번역 : 오름차순으로 정렬 된 정수 배열이 주어지면 주어진 대상 값의 시작 및 끝 위치를 찾습니다. O(N)의 시간복잡도로 해결해봅니다.

 

 

1. 접근 아이디어 

 

• 첫 번째 방법 : Index 0을 시작으로 target과 같은 값을 가지는 Index를 result 배열에 저장합니다. 각 Index에서 한 번의 Index만을 설정하기 때문에 예외를 처리해 줍니다. (target과 같은 값이 1개일 때 주의)
• 두 번째 방법 : 이진 탐색을 사용하여 target에 해당하는 Left index와 Right Index를 구해줍니다. target에 해당하는 값이 없을 때를 예외 처리해 줍니다.

 

2. 소스코드

 

• O(N) Complexity

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int index = 0;
        for(int i=0; i<nums.length; i++) {
            if(nums[i] == target) {
                if(index == 0) result[index++] = i;
                else if(index > 0) result[1] = i;
            }
        }
        if(result[0] != -1 && result[1] == -1) result[1] = result[0];
        return result;
    }
}

 

 

• O(logN) Complexity

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int left = binarySearch(nums, target, true);
        if(nums.length == 0 || left == nums.length || nums[left] != target) return result;
        result[0] = left;
        int right = binarySearch(nums, target, false) - 1;
        result[1] = right;
        return result;
    }

    public int binarySearch(int[] nums, int target, boolean isLeft) {
        int left = 0;
        int right = nums.length;
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] > target || (isLeft && nums[mid] == target)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}