[LeetCode] 35. Search Insert Position

https://leetcode.com/problems/search-insert-position/

Search Insert Position - LeetCode

Search Insert Position - Easy

 

간단한 이진탐색 문제다.

단, 추가조건은 target이 배열에 없을 경우엔 정렬된 상태에서 target이 어디에 추가되어야 하는지 구해야 한다.

이진탐색을 진행하면 mid m은 target의 index 또는 target과 가장 가까운 수의 index를 나타내게 된다.

이 때, nums[m]==target 이라면 m을, nums[m] < target 이라면 nums[m] 뒤에 target이 들어가야 하므로 m+1을,

nums[m] > target이라면 target 앞에 들어가야하므로 m을 리턴해주면 된다 (m-1을 리턴하는것이 아니다. m자리에 들어가면 한칸씩 밀릴 것이므로.)

 

전체 풀이 코드

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