[리트코드] 34. Find First and Last Position of Element in Sorted Array - js (투포인터)

1. 문제

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

2. 코드

처음 짠 코드) 오답

이 문제를 보고 투포인터로 풀어야겠다고 생각한 것은 정답이였고, 참 잘한 일이였다. 하지만 이 문제는 mid 값을 찾는 다른 투포인터 문제들과는 다른 성격을 띄는 문제라 이런 식으로 접근해서는 안됐었다.

var searchRange = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    let start = -1;
    let end = -1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            if (mid < start || start === -1) start = mid;
            if (mid > end || end === -1) end = mid;
        }
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] >= target){
            right = mid - 1;
        }
    }

    return [start, end];
};

mid 값이 target 값과 같아도, 앞 뒤로 target 값과 같은 요소들이 충분히 더 있을 가능성이 있었기 때문에 첫번째 if문에서 left와 right를 어떻게 처리해줘도 정답이 나오지 않았다. 생각해보니 현재 mid 값의 앞 또는 뒤 어디에 target 값과 같은 값들이 몇개나 있을지도 모르는데, 앞/뒤 탐색을 하나의 조건으로 처리하는 것 자체가 맞지 않았다.

즉, 시작점과 끝점의 탐색 처리를 따로 해주어야 했었다.

정답)

그래서 정답 코드에서는 시작점, 끝점 탐색 탐색 함수를 분리해 따로 처리해준다.

var searchRange = function(nums, target) {
    const findStart = (nums, target) => {
        let start = -1;
        let left = 0;
        let right = nums.length - 1;
        
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            // target값과 같은 지점 찾으면 right만 왼쪽으로 옮겨가며
            // target값과 같지만 가장 작은 인덱스 찾기
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
            
            if (nums[mid] === target) {
                start = mid;
            }
        }
        
        return start;
    };
    
    const findEnd = (nums, target) => {
        let end = -1;
        let left = 0;
        let right = nums.length - 1;
        
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            // target값과 같은 지점 찾으면 left만 왼쪽으로 옮겨가며
            // target값과 같지만 가장 큰 인덱스 찾기
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            
            if (nums[mid] === target) {
                end = mid;
            }
        }
        
        return end;
    };
    
    const start = findStart(nums, target);
    const end = findEnd(nums, target);
    
    return [start, end];
};