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

문제링크

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

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

 

 

 

문제정보

 

내림차순으로 정렬된 정수 요소로 이루어진 배열과 정수 target이 매개변수로 주어집니다.
배열에서 target값을 가진 index를 찾을 수 없으면 [-1, -1]을 반환합니다.
시간복잡도 O(log n)으로 알고리즘을 작성합니다.

example
입력: 숫자 = [5,7,7,8,8,10], 대상 = 8
출력: [3,4]

입력: 숫자 = [5,7,7,8,8,10], 대상 = 6
 출력: [-1,-1]

 

---

나의 풀이

var searchRange = function(nums, target) {
    return [nums.indexOf(target),nums.lastIndexOf(target)]
};

 

indexOf와 lastIndexOf를 이용하면 아주 쉽게 답을 구할 수 있습니다.

이런 풀이가 가능한 이유는 둘 모두 해당하는 값이 없으면 -1을 리턴한다는 특징을 가지고 있고

 

indexOf는 문자열의 앞에서부터 해당요소를 탐색하며 가장 먼저 찾은 인덱스를 반환하면서

반대로 lastIndexOf는 문자열의 뒤에서부터 해당요소를 탐색하며 가장 먼저 찾은 인덱스를 반환하기 때문입니다.

 

---

다른 사람의 풀이

이진탐색 알고리즘을 활용한 풀이입니다

코드길이는 제 풀이보다 길어지지만

이진탐색 알고리즘을 실제로 구현하는 방법을 알 수 있어서 참고용으로 가져와봤어요

 

var searchRange = function(nums, target) {
    let low = 0, high = nums.length-1, mid;
    
    // find the start
    while(low <= high) {
        mid = Math.floor((low+high)/2);
        if(nums[mid] >= target) high = mid-1;
        else low = mid+1;
    }
    
    // if target doesnt exist
    if(nums[low] !== target) return [-1, -1];
    
    const start = low;
    
    // reset low and high
    low = 0, high = nums.length-1;
    
    // find the end
    while(low <= high) {
        mid = Math.floor((low+high)/2);
        if(nums[mid] <= target) low = mid+1;
        else high = mid-1;
    }
    return [start, high];
};

이진탐색은 updown 게임과 유사해요!
Math.floor()는 소수점을 버려주는 함수이구요

 

코드를 차근차근 보면
(low + high) / 2 를 하면 배열의 중앙값에 위치하게될것입니다.
만약 배열의 중앙 인덱스의 값이 타겟과 비교해서 크거나 같다면
high = mid-1을 할당해줍니다.
그렇지 않다면 target값은 중앙값보다 작다는 뜻이기때문에
low = mid +1을 할당해줍니다.

while문은 low와 high가 같거나 low가 high보다 더 커지기 전까지 동작하므로
위 탐색을 계속하면 target값을 찾을 수 있을 것입니다.