[Java] 35. Search Insert Position

문제 설명 :

- 1차원 int 배열과 target 숫자를 주고, target이 배열내에 존재하면, 해당하는 Index를 return

- 존재하지 않으면, 정렬에 맞춰 삽입되어야 하는 index를 return하는 문제이다.

- 조건으로는 시간복잡도가 O(log n) 보다 작아야하는 조건이기 때문에 이진탐색과 해시맵 등을 활용할 수 있는데, 이진탐색으로 해결해보았다.

 

class Solution {
    public int searchInsert(int[] nums, int target) {
        //binary search :: O(log N)

        int left = 0;
        int right = nums.length -1;

        while(left <= right) {
            int mid = (left+right) / 2;

            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
}

 

해설 :

- 이진 탐색 알고리즘에 맞춰 left, right 를 설정하고, 두 값을 좁혀나가며 target에 접근한다.

- 이때, 값이 없다면 결과적으로 left가 right보다 커지게 되는데, 그때 left를 return하면 이 index가 target이 삽입되어야하는 위치가 된다.