LeetCode 35. Search Insert Position 자바 문제 풀이

문제

Search Insert Position - LeetCode

문제 해결 방법

• 주어진 문제의 잇풋은 정렬된 어레이입니다.
• O(log n)안에 풀어야 된다는 조건이 있습니다.
• 이미 정렬된 리스트에서 log n으로 찾는 방법은 이진검색(binary search)뿐입니다.
• 이 문제는 이진검색에 대해서 잘 알고, 이를 구현할수 있느냐고 묻는 문제입니다.
• 또한 이진검색을 구현시, 재귀함수를 사용할지 반복문을 사용할지 선택해야 합니다.
• 이 문제는 이전단계의 결과가 필요하지 않고, 하위문제로 분리할 필요도 없으므로, 반복문으로 구현하는것이 효과적입니다.
• 값을 찾지 못했을떄, 가장 가까운 값을 리턴해야 하므로, low값을 리턴합니다. mid값은 변경전이고, mid값에서 2를 나누고 남은 값은 버림을 하므로, high보다 low가 더 가깝습니다.

Github Link

https://github.com/eunhanlee/LeetCode_35_SearchInsertPosition_Solution.git

시간복잡도: O(), 공간복잡도: O()

class Solution {
    /**
     * 주어진 정렬된 배열에서 타겟 값의 삽입 위치를 검색합니다.
     *
     * @param nums   정렬된 정수 배열입니다.
     * @param target 검색할 값입니다.
     * @return 타겟이 삽입되어야 할 인덱스를 반환합니다.
     */
    public int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == target)
                return mid; // 타겟 값이 존재하는 경우, 해당 인덱스를 반환합니다.
            else if (nums[mid] < target)
                low = mid + 1; // 타겟이 현재 중간 값보다 큰 경우, 오른쪽 반구로 이동합니다.
            else
                high = mid - 1; // 타겟이 현재 중간 값보다 작은 경우, 왼쪽 반구로 이동합니다.
        }

        // 반복문을 벗어난 경우, 타겟이 존재하지 않는 경우 low 변수가 삽입 위치를 나타냅니다.
        return low;
    }
}