[LeetCode] Search for a Range ( by using JavaScript )

문제

https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/

Explore - LeetCode

 

How to Solve ?

 

[1] Binary Search

 

(log n) 이라는 시간 복잡도를 지켜야 하기에, 이진 탐색을 진행 하였다.

 

주어진 값을 찾는 것만이 아닌 같은 값이 있을 때, 그 배열의 시작과 끝을 저장 해야 하기에 꽤나 어려웠던 문제인 것 같다.

실제로도 방법을 찾던 도중, 찾아서 풀게 되었는데 풀이 방법이 너무 좋아 공유 차원으로 블로그에 기재 하게 되었다.

 

 

function solution(nums, target) {
  
  let n = nums.length;

  const binarySearch = function (isLeft) {
    let left = 0;
    let right = n;

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

      if (nums[mid] > target || (isLeft && nums[mid] == target)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }

    return isLeft ? left : right - 1;
  };

  let leftBoundary = binarySearch(true);
  let rightBoundary = binarySearch(false);

  if (nums[leftBoundary] != target || nums[rightBoundary] != target) {
    return [-1, -1];
  } else {
    return [leftBoundary, rightBoundary];
  }

}

const nums = [5, 7, 7, 8, 8, 10];
const target = 8;
console.log(solution(nums, target));