정렬된 숫자 배열이 주워지고 찾고자하는 값이 주어진다.
찾고자하는 값의 처음 인덱스와 마지막 인덱스를 구하는 문제. O(log n)
O(logn) 으로 풀기위해서
이진탐색
을 이용함.
가장 왼쪽의 인덱스를 구하는 이진탐색과 가장 오른쪽의 타겟을 찾는 이진탐색 함수를 만들어서 값을 구한다.
이때 구한 인덱스 값이 타겟값과 같은지 확인해 배열내에 타겟값이 존재하는지 여부를 확인.
/**
* @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]
}