[LeetCode/easy/Array] Search Insert Position

 

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

Search Insert Position - LeetCode

 

target value의 index 출력하기

여기서 문제는 만약 배열 안에 target value가 없을 경우다.

 

target value가 있는지 없는지는 find 함수를 통해 iterator를 구하면 distance 함수를 사용해서 위치를 출력할 수 있다.

그런데 만약 target value가 없을 경우, 이 배열에 있었다면 어디였을까? 를 구해야 하기 때문에 lower_bound 함수를 사용해서 target value보다 크거나 같은 첫 번째 원소가 몇 번째 인덱스에서 나오는지 반환한다.

 

 

lower_bound

: 찾으려는 key 보다 크거나 같은 첫번째 원소의 인덱스 (오름차순 정렬 필수)

lower_bound(nums.begin(), nums.end(), target) - nums.begin()

 

upper_bound

: 찾으려는 key 보다 큰 첫번째 원소의 인덱스 (오름차순 정렬 필수)

upper_bound(nums.begin(), nums.end(), target) - nums.begin()

 

---

 

int searchInsert(vector<int>& nums, int target) {
    auto it = find(nums.begin(), nums.end(), target);
    if(it != nums.end()) return distance(nums.begin(), it);
    return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}