주어진 배열에서 타겟으로 주어진 숫자값을 찾는 문제.
이때 타겟값이 없다면 타겟값을 삽입했을때 와야할 인덱스를 반납한다.
O(logn) 으로 풀기위해서
이진탐색
을 이용함.
이진탐색을 이용하여 문제를 해결한다.
이때 조건을 왼쪽 인덱스는 target
보다 작게 조건을 정의하고 오른쪽 인덱스를 target
을 포함한 높은 값으로 조건을 잡아주면 해당 문제를 해결할 수 있다.
오른쪽 값은 타겟이 있을경우 타겟값을 아닐경우 타겟이 올 수 있는 인덱스를 반납하게된다. (타겟과 가장 근접한 큰 수의 위치이기 때문에)
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
function binarySearch (left, right) {
while(left < right) {
const mid = Math.floor((left + right) / 2)
if (nums[mid] < target) left = mid + 1
else right = mid
}
return right
}
return binarySearch(0, nums.length)
};