LeetCode 35 Search Insert Position 풀러가기

문제

정렬된 배열 nums과 target이 주어진다. nums 배열에서 target이 있다면 그 index를 반환하고, 없다면 target이 정렬된 nums의 순서에 맞게 어디에 들어가면 되는지 index를 반환하면 되었다.

문제 분석

첫번째 시도

정렬된 배열을 주었으니, 이분탐색으로 풀면 될 것 같았다.

left는 0 으로, right는 nums의 마지막 요소로 초기화를 하였다.

그 후 left가 right보다 커질때까지 while 문을 수행하도록 했다.

left가 right보다 커지면 target이 mid 보다 크다는 것이니, mid+1로 갱신된 left index를 반환하면 되었다.

코드

class Solution {
    public int searchInsert(int[] nums, int target) {
        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;
    }
}

결과 : 성공

Runtime

Memory

문제가 O(log n)으로 작성하라고 되어 있어서 인지, Runtime은 0ms 가 아니면 통과 안시켜주는 것 같았다. 다른 사람과 비교를 위한 그래프는 제공해주지 않았다.