-
[c++] lower_bound, upper_bound 함수Programming/c++ 2022. 9. 15. 14:36728x90
lower_bound, upper_bound 란?
c++에서 이진 탐색으로 원소를 탐색하는 기능을 합니다.
lower_bound
찾으려는 target 값보다 같거나 큰 숫자 가 배열 몇 번째에서 처음 등장하는지 찾는 함수
-사용 조건 : 탐색을 진행할 배열 및 벡터는 오름차순으로 정렬되어 있어야 한다.
lower_bound 예제
int arr[6] = { 1,2,3,4,5,6 }; int index = lower_bound(arr, arr + 6, 6) - arr;
#include <string> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> nums = { 1,3,5,6 }; int target = 4; auto a = lower_bound(nums.begin(), nums.end(), target); int index = a - nums.begin(); return 0; }
▶nums 시작 부터 끝까지 탐색하면서 target 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환하는 예제입니다.
→nums 벡터에서 target 은 nums[1] , nums[2] 사이의 숫자 입니다.
▶ lower_bound의 반환형은 iterator이므로 실제 index를 구하려면
lower_bound값에서 벡터의 첫번째 주소를 가르키는 주소(iterator)를 빼 주면 됩니다.
upper_bound
찾으려는 target 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾는 함수
- 사용 조건 : 탐색을 진행할 배열 및 벡터는 오름차순으로 정렬되어 있어야 한다.
upper_bound 예제
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> nums = { 1,3,5,6 }; int target = 5; auto b = upper_bound(nums.begin(), nums.end(), target); int index2 = b - nums.begin(); // = 3 return 0; }
▶ 벡터의 처음부터 끝까지 탐색하면서 target 값인 5를 처음으로 초과하는 원소의 index번호를 반환하는 예제입니다.
→ 5를 처음 초과하는 원소는 6이므로 index = 3, 따라서 결과는 3 입니다.
활용 문제
오름차순 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색하고자 할 때
▶이진 탐색 기반의 lower_bound, upper_bound를 사용하면 시간 복잡도를 효과적으로 줄일 수 있습니다.
▶예제 : { 1,3,5,5,7,8,8,10,10,11,13} 에서 5이상 11이하의 숫자가 몇 개인지 구하시오
int main() { vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 }; int result = upper_bound(arr.begin(), arr.end(), 11) - lower_bound(arr.begin(), arr.end(), 5); return 0; }
arr 벡터는 오름차순으로 정렬되어 있어야한다.
5이상 11이하의 수의 개수를 구하기 위해
(11을 초과하는 첫번째 원소의 index) - (5 이상인 원소의 첫번째 index) 를 계산하면 된다.
오름차순 정렬된 자료에서 특정 숫자가 몇 번 나오는지 탐색하고자 할 때
▶이진 탐색 기반의 lower_bound, upper_bound를 사용하면 O(lon N) 으로 탐색 가능하다.
▶예제 : { 1,3,5,5,7,8,8,10,10,11,13} 에서 5의 개수를 구하시오
int main() { vector<int> arr = { 1,3,5,5,5,8,8,10,10,11,13 }; int result = upper_bound(arr.begin(), arr.end(), 5) - lower_bound(arr.begin(), arr.end(), 5); return 0; }
5의 개수를 구하기 위해
(5를 초과하는 첫번째 원소의 index) - (5 이상인 원소의 첫번째 index)를 계산하면 된다.
728x90'Programming > c++' 카테고리의 다른 글
[c++] smart pointer (unique_ptr, shared_ptr, weak_ptr) (0) 2022.09.22 [c++] std::max_element , std::min_element 함수 (0) 2022.09.16 [c++] unique 함수 (0) 2022.08.01 [c++] std::accumulate 함수 vector sum (0) 2022.07.16 [c++] Visual Studio Code c++ 설정 (0) 2022.06.26