leeCode (Search Insert Position) -Array

문제

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

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

 

---

배경지식

배열 : 메모리 상에 원소를 연속하게 배치한 자료구조

 

특징 : 

• 추가적으로 소모되는 메모리의 양이 거의 없음
• Cache hit rate가 높음
• 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

시간복잡도 :

• 임의에 위치에 있는 원소를 확인 / 변경 O(1)
• 끝에 원소를 추가 / 제거 O(1)
• 임의에 위치에 있는 원소를 추가 / 제거 O(N)

 

문제해결

1. 시작 인덱스(S)가 끝 인덱스(E)보다 작을 때만 반복을 한다.

2. S와 E의 중간 지점(M)을 탐색한다.

3. target > M => M+1 ~ E 범위로 변경해서 M을 다시 구한다.

4. target < M => S ~ M-1 범위로 변경해서 M을 다시 구한다.

5. target == M => M을 리턴한다.

6. 반복이 다 될때까지 target을 찾지 못하면, 조건에 맞게 M을 return 해준다.

 

구현

var searchInsert = function (nums, target) {
    let startIndex = 0;
    let endIndex = nums.length - 1;
    let middleIndex = 0;
    while (startIndex <= endIndex) {
        middleIndex = Math.round((startIndex + endIndex) / 2)
        if (target < nums[middleIndex]) endIndex = middleIndex - 1;
        else if (target > nums[middleIndex]) startIndex = middleIndex + 1;
        else if (target === nums[middleIndex]) return middleIndex;

    }
    return nums[middleIndex] > target ? middleIndex : middleIndex + 1
};