C++ 35. Search Insert Position(Leet Code)

Leet Code_35. Search Insert Position

Binary Search

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

주어진 원소를 정렬된 vector내 맞는 위치를 찾기​

방법

1. 주어진 원소와 맞는 값이 있으면 해당 index를

2. 없으면 적절한 위치의 index를

결과

주어진 원소를 정렬된 vector내 맞는 위치를 찾기​

 

통과한 코드

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

생각보다 금방 풀었던 문제

target과 start, end를 vector의 index로 하여 접근했고 target의 값에 따라 start, end값을 바꾸어 주었다.

여기서 잘못했던 점은 mid값을 바꿀 때 start+1, end-1로 바꾸어 줬어야 했다~~~~~