구별되는 정수 및 대상 값의 정렬된 배열이 주어지면 대상이 발견되면 인덱스를 반환, 그렇지 않은 경우 인덱스를 순서대로 삽입한 경우 인덱스를 원래 위치에 반환
O(log n) 런타임 복잡도로 알고리즘을 작성해야한다
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function (nums, target) {
if (nums.findIndex((el) => el === target) === -1) {
nums.push(target);
nums.sort((a, b) => a - b);
}
return nums.findIndex((el) => el === target)
};nums 배열안에 target이 있는 경우 , 아닌 경우로 나누어 없는 경우 추가하고 다시 정렬해서
target의 index를 찾음
⇒ 이진 탐색으로 nums 배열안에 없는 경우에 추가하는 로직을 변경,
이진탐색으로 target의 index값을 찾는다면 런타임을 줄일 수 있을 것으로 보임
최다 추천 코드
function searchInsert(nums, target) {
return binarySearch(nums, target, 0, nums.length - 1);
};
function binarySearch(array, target, start, end) {
// If the target is less then the very last item then insert it at that item index
// because anything index less then that has already been confirmed to be less then the target.
// Otherwise insert it at that item index + 1
// because any index grater then that has already been confirmed to be greater then the target
if (start > end) return start;
const midPoint = Math.floor((start + end)/2);
// found target
if (array[midPoint] === target) return midPoint;
// search the left side
if (array[midPoint] > target) return binarySearch(array, target, start, midPoint - 1);
// search the right side
if (array[midPoint] < target) return binarySearch(array, target, midPoint + 1, end);
}⇒ 이진 탐색 사용
