[leetcode] 34. Find First and Last Position of Element in Sorted Array - 자바스크립트 0607

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] 두가지의 변수가 주어진다.

nums라는 정렬 안에 target이 들어있다고 하면, nums에서의 시작위치와 끝 위치를 return 하는 문제이다.

만일, nums에 target이 없다고 하면 [-1, -1]을 return한다.

1. Boundary Condition을 적는다면, nums가 빈 정렬이면 [-1, -1]을 return 한다.

    if (nums.length === 0) return [-1, -1]

2. nums는 숫자로 정렬되어 있기 때문에, target이 nums[0]보다 작거나, nums[nums.length-1]보다 크면 [-1. -1]을 정렬한다

    if (nums[start] > target || nums[end] < target) return [-1, -1]

 

문제 풀이를 위해 Binary Search를 적용한다

    while (start <= end) {
        let mid = Math.floor((start + end) / 2)
        if (nums[mid] <= target) {
            res = mid
            start = mid + 1
        } else {
            end = mid - 1
        }
    }

이 Binary Search를 적용하여 얻는 값은 res이다.

res는, start와 end가 서로 크기가 같거나 end가 start보다 작아진 경우 target이 없는 것이기 때문에, 이 경우에는 return [-1, -1]을 해야한다

    if (nums[res] !== target) return [-1, -1]

target이 여러개인 경우와 한개인 경우 두가지인 경우가 있다. 이 위치를 표시하기 위해서

    let p1 = res
    let p2 = res

두개의 점을 잡고

    while (nums[p1] === target) {
        p1 -= 1
    }
    while (nums[p2] === target) {
        p2 += 1

    }

target이 아닐 때까지 p1은 -1, p2는 +1을 적용한뒤

    return [p1 + 1, p2 - 1]

값을 리턴해준다. 이때 각각 +1, -1을 해주는 이유는, 값이 달라질때까지 값을 변화시키기 때문에 target과 같은 값을 return 하려고하면 p1+1, p2-1을 해줘야한다.

전체 풀이이다

var searchRange = function (nums, target) {
    let start = 0
    let end = nums.length
    let res = 0
    if (nums.length === 0) return [-1, -1]
    if (nums[start] > target || nums[end] < target) return [-1, -1]
    while (start <= end) {
        let mid = Math.floor((start + end) / 2)
        if (nums[mid] <= target) {
            res = mid
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    if (nums[res] !== target) return [-1, -1]
    let p1 = res
    let p2 = res
    while (nums[p1] === target) {
        p1 -= 1
    }
    while (nums[p2] === target) {
        p2 += 1
    }
    return [p1 + 1, p2 - 1]
};