[Algorithm] Leetcode 34. Find First and Last Position of Element in Sorted Array (java)

풀이 코드

class Solution {
     public int[] searchRange(int[] nums, int target) {
        boolean isStart = true;
        
        int[] ans = new int[2];
        ans[0] = getStartOrEnd(isStart, target, nums);
        ans[1] = getStartOrEnd(!isStart, target, nums);
        return ans;            
    }
    
     public int getStartOrEnd(boolean isStart, int target, int[] nums){ 
        int left = 0;
        int right = nums.length - 1;
        int num = -1; 
    
        while(left <= right){
            int mid = left + (right - left) / 2;  
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                if(isStart){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
                num = mid;
            }       
        }
        return num;   
    }
}

 

 

사고 과정

오늘도 array,, 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

 

O(log N)의 시간복잡도로, 주어진 sorted array 'nums' 안의 target의 구간을 반환해주면 되는 문제!!

(만약 target이 존재하지 않는다면 [-1, -1]을 반환!

 

문제에서 노골적으로 O(logN)을 요구하는데 Binary Search를 안 쓸 이유가 없을 것 같다. 

 

지난번 Binary Search 문제와 접근법은 동일하지만, 

https://highandbrightdev.tistory.com/entry/A100C-Leetcode-704-Binary-Search-java

[A100C_day 1] Leetcode 704. Binary Search (java)

문제는 target이 여러개 존재하는 경우, 그 범위를 반환해줄 때인 것 같은데, 

 

기껏 binary search 로 target을 찾아놓고, linear하게 target의 범위를 찾는다면, 최악의 경우 O(N)의 시간복잡도가 걸린다. 

(nums의 요소들이 모두 target일 경우, 결국 시간 복잡도는 O(N)이므로..!!)

 

따라서 target의 범위도 binary search를 이용해서 찾으면 되는 문제!!

 

코드 상의 특이한 점이라면 getStartOrLast 메서드를 따로 선언해서 target의 범위를 구했다는 점. 

그 외에는 앞선 binary search 문제와 동일하다!

 

오알완..!