[ Top Interview 150 ] 35. Search Insert Position

문제

35. Search Insert Position

  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.

• Input
  • 중복되지 않고 오름차순으로 정렬되어 있는 int 배열 nums
  • 삽입해야 하는 원소 target
• Output
  • target이 nums안에 있다면, 해당 index를 반환
  • target이 nums안에 없다면, 삽입해야 할 index를 반환
• Condition
  • Time complexity : O(logN)
• Example
  • Input: nums = [1,3,5,6], target = 5; Output: 2
  • Input: nums = [1,3,5,6], target = 2; Output: 1
  • Input: nums = [1,3,5,6], target = 7; Output: 4

알고리즘 전략

• Binary Search

  • 정렬된 알고리즘에서 사용할 수 있는 Search Algorithm
  • 중간에 있는 원소와 찾고자 하는 원소의 크기를 비교한 후에, 그 결과에 따라 찾는 범위를 절반으로 줄이는 방법
  • Time complexity : O(logN)

• 해당 문제가 Binary Search가 어울리는 이유

  • 이미 "정렬"되어 있는 "1차원 배열"을 제공하였음
  • 특정 원소가 들어갈 "위치를 찾아야함"

• 기본 전략

  • Binary Search를 이용하여 특정 원소를 찾아나감
  • 해당 원소가 있다면 그 위치를 반환하고, 해당 원소가 없다면 그 원소보다 크면서 가장 앞에 있는 원소의 위치를 반환

초안 작성

• Binary Search라고 해도 front, behind pointer를 이동시키는 것에는 주의를 해야한다.

• 문제점

  • 기본적으로 'Binary Search'는 nums 범위 안에 target이 존재한다는 전제를 한다.
  • 즉, target이 nums 범위 밖에 있다면, front, behind를 통해서만 위치를 알 수 없다.
  • 위의 Example Input: nums = [1,3,5,6], target = 7; Output: 4를 통과하지 않는다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        
        int front = 0;
        int behind = nums.length - 1;

        while (front < behind - 1) {
            int middle = (front + behind) / 2;
            
            if (target < nums[middle]) {
                behind = middle;
            } else if (target > nums[middle]){
                front = middle;
            } else {
                return middle;
            }
        }
        
        return front + 1;
    }
}

1차 답안

• 초안에서 계산된 결과에서 target이 nums 범위 안에 있는지 확인하는 과정을 추가했다.

• Complexity

  • Time complexity : O(logN)
  • Space complexity: O(1)

class Solution {
    public int searchInsert(int[] nums, int target) {
        
        int front = 0;
        int behind = nums.length - 1;

        while (front < behind - 1) {
            int middle = (front + behind) / 2;
            if (target < nums[middle]) {
                behind = middle;
            } else if (target > nums[middle]){
                front = middle;
            } else {
                return middle;
            }
        }

        if (target > nums[behind]) {
            return behind + 1;
        } else if (target <= nums[front]) {
            return front;
        }
        return front + 1;
    }
}

2차 답안

• 리팩토링 포인트

  • 초안에서 부족한 점을 추가하보니, if-else 등의 분기점이 많아짐

• 수정 전략

  • while 문에서 index가 1차이 가 아니라, 내가 원하는 원소를 front, behind가 모두 가리키도록 만들어 분기문을 줄였다.
  • target이 nums의 가장 뒤에 오는 경우를 설명할 수 없어 초기에 예외 처리 형식으로 설정하였다.

• Complexity

  • Time complexity : O(logN)
  • Space complexity: O(1)

class Solution {
    public int searchInsert(int[] nums, int target) {

        if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        
        int front = 0;
        int behind = nums.length - 1;

        while (front < behind) {
            int middle = (front + behind) / 2;
            int middleValue = nums[middle];

            if (target > middleValue) {
                front = middle + 1;
            } else {
                behind = middle;
            }
        }

        return front;
    }
}