[leetcode] 35. Search Insert Position - array

https://leetcode.com/problems/search-insert-position/description/

 

고유 정수의 정렬된 배열과 목표값이 주어졌을 때, 목표값이 발견되면 인덱스를 반환합니다. 

그렇지 않은 경우 순서대로 삽입했을 때 인덱스가 있을 위치를 반환합니다. 

런타임 복잡도가 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

 

 

일단 돌아가게 만들었지만... 시간 복잡도 때문에 리팩토링 해야한다..

function searchInsert(nums: number[], target: number): number {
  
    if (nums.includes(target)) { return nums.indexOf(target) }
    else {
        let idx = 0
        for(let i = 0; i < nums.length; i++) {
            idx++
            if(nums[i] > target) return i
        }
        return idx
    }
};

추가로 includes()와 indexOf() 메서드도 각각 O(n) 시간 복잡도를 가지게 되고,

for 루프로 인해 선형검색을 하고 있습니다.

 

1. O(log n)의 시간 복잡도를 갖게 구현하라고 하였고

2. 정렬된 배열이므로

👉 이진 탐색(Binary Search) 을 사용하면 된다.

 

function searchInsert(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        // target과 일치하면 해당 인덱스를 반환합니다.
        if (nums[mid] === target) {
            return mid;
     
        } else if (nums[mid] < target) {    // target이 더 크면 왼쪽 절반을 버리고 오른쪽을 검색
            left = mid + 1;
        } else { // target이 더 작으면 오른쪽 절반을 버리고 왼쪽을 검색
            right = mid - 1;
        }
    }
    // 여기서 left 는
    // target과 같은 값을 찾았을 때는 그 위치
	// target을 찾지 못했을 때는 target보다 큰 첫 번째 원소의 위치
    return left;
}