[Leetcode] 34. Find First and Last Position of Element in Sorted Array

#이진탐색

Problem

문제 링크

정렬된 숫자 배열이 주워지고 찾고자하는 값이 주어진다.
찾고자하는 값의 처음 인덱스와 마지막 인덱스를 구하는 문제. O(log n)

Solution

O(logn) 으로 풀기위해서 이진탐색을 이용함.

가장 왼쪽의 인덱스를 구하는 이진탐색과 가장 오른쪽의 타겟을 찾는 이진탐색 함수를 만들어서 값을 구한다.
이때 구한 인덱스 값이 타겟값과 같은지 확인해 배열내에 타겟값이 존재하는지 여부를 확인.

JS Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
  
  function getLeftIndex () {
    let left = 0, right = nums.length
    while (left < right) {
      const mid = Math.floor((left + right) / 2)
  
      if (nums[mid] < target) left = mid + 1
      else right = mid
    }
    return left
  }

  function getRightIndex () {
    let left = 0, right = nums.length
    while (left < right) {
      const mid = Math.floor((left + right) / 2)
  
      if (nums[mid] <= target) left = mid + 1
      else right = mid
    }
    return left -1
  }

  const left = getLeftIndex()
  const right = getRightIndex()
  if (nums[left] !== target) return [-1,-1]
  return [left,right]
}