35. Search Insert Position

문제 파악 및 재정의

중복없는 정수로 이루어진 정렬된 배열과 목표 값이 주어진다.
목표를 찾으면 해당 index를 반환
목표 없다면 들어갈 적합한 자리의 index를 반환하라

자료구조 및 알고리즘 선택

배열 순회 / 그리디?

구현

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

 

회고

순회 중 target값이 나오거나 그것보다 큰 값으로 넘어간다면 해당 index를 반환

예외는 타겟이 가장 큰 값일 경우가 있는데 이 경우를 위해 반환값에 배열의 마지막 위치를 미리 명시해줬다.

 

배열과 Binary Search 문제였다.

o(n)이지만 더 줄일 수 있는 방법이 있을 것 같다.

---

Time complexity: O(logn)
Space Complexity: O(1)

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end-start)/2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) end = mid-1;
            else start = mid + 1;
        }

        return start;
    }
}