35. Search Insert Position

문제 정의 

주어진 정렬된 배열에서 목표 값을 찾고, 찾지 못하면 목표 값이 삽입될 인덱스를 반환하는 문제입니다. 이 문제는 O(log n) 시간 복잡도로 해결해야 합니다. 

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

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 

접근 방법 소개

처음에는 순차 접근 방식을 사용하여 문제를 해결했습니다. 하지만 이 방식은 O(n) 시간 복잡도를 가지며, 이는 문제의 요구사항인 O(log n)에 부합하지 않습니다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i=0; i<nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
            if (target <nums[i]) {
                return i;
            }
        }        
        return nums.length;
    }
}

 

다음으로, 이진 탐색을 사용하여 문제를 해결했습니다. 이진 탐색은 O(log n) 시간 복잡도를 가지며, 대규모 데이터 처리에 매우 효율적입니다.

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

 

이진 탐색 알고리즘 상세 설명

이진 탐색은 배열의 중간 값을 선택하여 목표 값과 비교하고, 목표 값이 더 크면 오른쪽 절반을, 더 작으면 왼쪽 절반을 다시 검색하는 방식입니다. 이렇게 반복함으로써 검색 범위를 절반으로 줄여나갑니다.

1. 초기화: left와 right 변수를 배열의 처음과 끝으로 설정합니다.
2. 중간값 계산: mid 변수를 left와 right의 중간값으로 설정합니다.
3. 비교: nums[mid]가 target과 같으면 mid를 반환합니다. nums[mid]가 target보다 작으면 left를 mid + 1로, nums[mid]가 target보다 크면 right를 mid - 1로 설정합니다.
4. 반복 종료: left가 right보다 커지면 반복을 종료하고, left를 반환합니다.

테스트 케이스 및 결과 검증

빈 배열 
int[] nums = {};
int target = 5;
// Expected output: 0

배열의 첫번째 위치에 삽입 
int[] nums = {2, 3, 5, 6};
int target = 1;
// Expected output: 0

배열의 마지막 위치에 삽입 
int[] nums = {2, 3, 5, 6};
int target = 7;
// Expected output: 4

배열의 중간에 삽입
int[] nums = {2, 4, 6, 8};
int target = 5;
// Expected output: 2

목표 값이 배열의 모든 요소와 일치
int[] nums = {2, 2, 2, 2};
int target = 2;
// Expected output: 0 

배열의 경계 값 
int[] nums = {2, 4, 6, 8};
int target = 2;
// Expected output: 0

int[] nums2 = {2, 4, 6, 8};
int target2 = 8;
// Expected output: 3

테스트 코드 
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return left;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Edge case 1: 빈 배열 
        System.out.println(sol.searchInsert(new int[]{}, 5)); // Expected output: 0

        // Edge case 2: 배열의 첫번째 위치에 삽입 
        System.out.println(sol.searchInsert(new int[]{2, 3, 5, 6}, 1)); // Expected output: 0

        // Edge case 3: 배열의 마지막 위치에 삽입 
        System.out.println(sol.searchInsert(new int[]{2, 3, 5, 6}, 7)); // Expected output: 4

        // Edge case 4: 배열의 중간에 삽입
        System.out.println(sol.searchInsert(new int[]{2, 4, 6, 8}, 5)); // Expected output: 2

        // Edge case 5: 목표 값이 배열의 모든 요소와 일치
        System.out.println(sol.searchInsert(new int[]{2, 2, 2, 2}, 2)); // Expected output: 0

        // Edge case 6: 배열의 경계 값 
        System.out.println(sol.searchInsert(new int[]{2, 4, 6, 8}, 2)); // Expected output: 0
        System.out.println(sol.searchInsert(new int[]{2, 4, 6, 8}, 8)); // Expected output: 3
    }
}