Daily Leetcoding Challenge 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

LeetCode - The World's Leading Online Programming Learning Platform

한글날에 풀어보는 코테 문제. 주말에 시간 내서 풀기가 참 어렵지만 그래도 한 문제는 풀었다. ㅎㅎ

 

직관

이진 검색을 통해 lower bound, upper bound를 찾는 문제와 유사하다. 주어진 배열 [1, 2, 2, 3, 3, 3, 4, 6]에서 lowerBound(3)의 값은 3이지만 upperBound(3)의 값은 6으로 내가 찾는 target값보다 처음으로 큰 값인 4의 인덱스를 리턴한다. 그래서 upperBound를 찾는 것이 아닌 target 원소의 마지막 인덱스를 찾아야 한다.

솔루션에서 참고한 아이디어를 이용해서 문제를 풀었는데, 직관적이면서 알고리즘 수행 속도도 빨라서(100%) 익혀두면 좋을 것 같다. 이진 탐색을 통해서 먼저 target 값이 출현한 인덱스를 저장하고, 그 인덱스를 기준으로 좌측, 또는 우측으로 범위를 줄여서 반복적으로 이진 탐색을 하는 방식이다. 이진 탐색 알고리즘들의 검색 범위가 대부분 [start, end)라서 기억하기 쉽도록 그 포맷에 맞춰서 구현했다.

접근법

target 값의 첫 번째 포지션을 찾는 함수를 호출한다. (first)

target 값의 마지막 포지션을 찾는 함수를 호출한다. (last)

{first, last}를 리턴한다.

복잡도

findFirst, findLast 함수가 각각 이진검색을 하고, 상수개의 변수를 사용하기 때문에 시간 복잡도는 O(logn), 공간 복잡도는 O(1)이다.

코드

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int first = findFirst(nums, target);
        int last = findLast(nums, target);

        return new int[]{first, last};
    }

    private int findFirst(int[] nums, int target) {
        int start = 0, end = nums.length;
        int first=-1;
        while(start < end) {
            int mid = start + (end-start)/2;
            if (nums[mid] == target) {
                first = mid;
                end = mid;
            } else if(nums[mid] > target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        
        return first;
    }

    private int findLast(int[] nums, int target) {
        int start = 0, end = nums.length;
        int last = -1;
        while(start < end) {
            int mid = start + (end-start)/2;
            if (nums[mid] == target) {
                last = mid;
                start = mid + 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return last;       
    }
}