[LeetCode] 34. Find First and Last Position of Element in Sorted Array

[Medium] 34. Find First and Last Position of Element in Sorted Array

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

Example 1

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

Example 2

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

문제 설명

33번 문제보다 훨씬 쉽다. 완전히 정렬된 배열이 주어지고, 찾는 값의 start index와 end index를 len 2인 배열로 반환한다. 없을 경우 -1을 채워 반환한다.

나의 풀이

O(logN)

1. O(logN)의 경우 Binary Search를 이용하면 풀 수 있다.
2. 일단 값을 찾은 경우, 좌측, 우측으로 while로 이동하여 start와 end index를 구한다.
3. 여러가지 제약조건을 넣어 코드가 지저분하지만 1ms의 속도를 가진다.
4. 최악의 상황으로, 만일 모든 값이 동일한 배열이 주어질 경우, O(N)이기 때문에, 각 방향으로 binary search를 수행하는 방법이 더 적합해 보인다. O(2logN)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int low = 0;
        int high = nums.length - 1;
        
        if(nums.length == 0){
            return result;
        }
        
        if(nums.length == 1 && nums[0] == target){
            result[0] = 0;
            result[1] = 0;
            return result;
        }

        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                int start = mid;
                int end = mid;
                while(start > 0 && nums[start-1] == target){
                    start--;
                }
                while(end < nums.length-1 && nums[end+1] == target){
                    end++;
                }
                result[0] = start;
                result[1] = end;
            }
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        if (nums[low] == target) {
            int start = low;
            int end = low;
            while(start > 0 && nums[start-1] == target){
                start--;
            }
            while(end < nums.length-1 && nums[end+1] == target){
                end++;
            }
            result[0] = start;
            result[1] = end;
        }


        return result;
    }
}