문제 푼 날짜 : 2021-11-26

문제

문제 링크 : https://leetcode.com/problems/search-insert-position/

접근 및 풀이

주어진 vector에 target 값이 존재하면 그 위치를 return 하고, 없다면 vector에 들어가게 될 index를 return 하는 문제였다.
문제를 읽자마자 직관적으로 O(n)으로 풀면되겠다 싶었지만, 문제의 조건이 O(logn) 이었으므로 binary search를 구현해주어 쉽게 풀 수 있었다.

코드

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        
        while (start <= end) {
            int mid = (start + end)/2;
            if (nums[mid] > target) {
                end = mid - 1;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return start;
    }
};

결과

피드백

오랜만에 기초 알고리즘 구현 문제를 푸니 한 번에 안떠오르는 경우가 있는데, 다시 많이 풀어 익숙해지도록 해야겠다.