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);
}
비교적 간단한 문제 였는듯.
'Leetcode > Top 100 Liked' 카테고리의 다른 글
| [Binary Search][Hard] 124. Binary Tree Maximum Path Sum (0) | 2024.03.07 |
|---|---|
| [Binary Search][Medium] 74. Search a 2D Matrix (1) | 2024.03.06 |
| [Binary Search][Medium] 34. Find First and Last Position of Element in Sorted Array (0) | 2024.03.05 |
| [Binary Search][Medium] 33. Search in Rotated Sorted Array (0) | 2024.03.03 |
| [Binary Search][Hard] 4. Median of Two Sorted Arrays (0) | 2024.03.03 |