[1주차] 35. Search Insert Position

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

Search Insert Position - LeetCode

---

📝 문제

정렬되고, 중복없는 정수가 담긴 배열 nums와, 정수 target 이 주어진다.

nums 에서 target 을 찾아 인덱스를 반환하고, 없으면 삽입 시 정렬을 유지할 수 있는 위치의 인덱스를 반환하라.

 

🎈 풀이

전형적인 이진탐색 문제. 탐색 실패시 인덱스를 반환하는 조건식만 추가하면 된다.

 

시간복잡도: O(n)

공간복잡도: O(1)

public int searchInsert(int[] nums, int target) {
    return binarySearch(nums, 0, nums.length - 1, target);
}

private int binarySearch(int[] nums, int left, int right, int target) {
    int mid = (left + right) / 2;
    if (nums[mid] == target) return mid;
    if (left == right) {
        if (nums[left] > target) return left;
        else return left + 1;
    }
    if (nums[mid] > target) return binarySearch(nums, left, mid, target);
    if (nums[mid] < target) return binarySearch(nums, mid + 1, right, target);
    return -1;
}

• 8행: 탐색을 완료하였으나 target을 찾지 못한 상태
• 9행: 현재 원소가 target 보다 크다. 그러므로 target은 현재 위치에 삽입하고, 원래 원소를 뒤로 밀면 정렬 된 상태이다.
• 10행: 현재 원소가 target 보다 작다. 현재 원소 바로뒤에 삽입하면 정렬된 상태이다.