(Leet Code JS)Find First and Last Position of Element in Sorted Array

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

 

이진 탐색 알고리즘 활용.

주어진 nums에서 target을 찾고, 해당 인덱스의 처음과 끝을 answer에 저장하면 된다.

만약 nums가 비어있다면 바로 리턴.

 

이진 탐색으로 front <= back일 때까지 target의 인덱스를 찾는다.

중복된 수가 들어갈 수 있기 때문에 가장 처음에 위치한 인덱스를 찾아준다.

만약 target이 있다면 found = true로 바꿔주어 찾았다는 flag를 변경해준다.

 

while 이후에는 found에 따라 값이 달라진다.

found가 false라면 찾지 못했기 때문에 [-1, -1]을 리턴하게 된다.

found가 true라면 front = first index가 된다.

이제 가장 마지막에 위치한 target의 인덱스를 for문을 이용해 찾고, answer을 리턴하면 된다.

var searchRange = function(nums, target) {
    const answer = [-1, -1];
    let front = 0;
    let back = nums.length;
    let found = false;
    
    if(!nums.length){
        return answer;
    }
    
    while(front <= back){
        const mid = Math.floor((front + back) / 2);
        
        if(nums[mid] < target){
            front = mid + 1;
        } else if(nums[mid] > target){
            back = mid - 1;
        } else{
            back = mid - 1;
            
            if(nums[mid] === target){
                found = true;    
            }
        }
    }
    
    if(found){
        answer[0] = front;
        
        for(let i = front; i < nums.length; i++){
            if(nums[i] === target){
                answer[1] = i;
            }
        }
    }
    
    return answer;
};