[Binary Search][Easy] 35. Search Insert Position

Leetcode/Top 100 Liked

[Binary Search][Easy] 35. Search Insert Position

자전거통학 2024. 3. 5. 23:30

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

Search Insert Position - LeetCode

Can you solve this real interview question? Search Insert Position - Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must w

leetcode.com

Q. 주진 정렬된 배열 nums에서 target value를 찾아 그 index를 반환하라. 없으면 target 이 있어야 할 위치를 반환하라.

Solution.

진행 조건 - 정렬된 배열의 목표값을 찾듯이 진행 하며 반대 side를 버린다.

완료 조건 - 값을 찾으면 완료된다.

또한, 못 찾았을때, 어떤 값을 취할 것인가. left는 커지고 right는 작아지는 방향으로 진행 하므로, 엇갈리면 left가 큰 값이 된다. 따라서 이 값이 target이 없을경우, 있어야 할 위치가 된다. 따라서 left를 반환한다.

로직대로 코드를 작성한다.

int searchInsertBS(vector<int>& nums, int target, int left, int right)
{
    if(left > right) return left;

    int mid = left + (right-left)/2;
    if(nums[mid] == target) return mid;
    else if(nums[mid] > target) return searchInsertBS(nums, target, 0, mid-1);
    else return searchInsertBS(nums, target, mid+1, right);
}

public:
int searchInsert(vector<int>& nums, int target) 
{
    return searchInsertBS(nums, target, 0, nums.size()-1);
}

비교적 간단한 문제 였는듯.