LeetCode 35 - Search Insert Position

https://leetcode.com/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-interview-150

 

정렬된 배열 nums와 숫자 target이 주어졌을 때 target이 nums에 있다면 해당 인덱스를 없다면 삽입되는 인덱스를 반환하라. 단 O(logN)의 시간복잡도로 풀이해야 한다.

 

간단하게 O(N)으로 순회하면서 파악하면 답을 구할 수 있다.

하지만 문제 조건에 O(logN)을 요구하고 있으므로 다른 방법을 찾아야 한다.

주어진 조건을 보면 nums 배열은 중복이 없고 오름차순으로 정렬된 배열이다. 따라서 이진탐색을 사용하면 O(logN)의 시간복잡도로 풀 수 있다.

사실 자바에 Collections에 있는 binarySearch 메서드가 이미 위의 조건을 구현하고 있다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        List<Integer> numbers = Arrays.stream(nums)
                                    .boxed()
                                    .collect(Collectors.toList());

        int idx =  Collections.binarySearch(numbers, target);
        return idx < 0 ? -idx - 1 : idx;
    }
}

그렇지만 위의 방법은 Collection에만 사용할 수 있으므로 배열을 List로 변경하는 작업이 추가된다.

따라서 이진탐색을 직접 구현하겠다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        
        while (l <= r) {
            int mid = l - (l - r) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else if (nums[mid] > target) {
                r = mid - 1;
            }
        }
  
        return l;
    }
}