정렬된 형태의 리스트가 존재할 때 특정 값보다 크거나 작은 수를 찾고자 하면 제목에 있는 함수를 적극 활용하기. 이진 탐색을 사용해 시간 복잡도가 O(logN)으로서 순차 탐색으로 찾는 것보다 훨씬 이득이다.
이진 탐색을 사용하므로 무조건 정렬되어 있는 상태에서 사용해야 한다.
lower_bound()는 주어진 값보다 같거나 큰 숫자의 위치를 반환해주고
upper_bound()는 주어진 값보다 큰 숫자의 위치를 반환해준다.
'코딩테스트 > C++' 카테고리의 다른 글
| C++ 함수에서 배열을 매개변수로 받거나 리턴할 때 (0) | 2024.03.27 |
|---|---|
| [ 백준 BOJ ] 10775 번 - 공항 (C++) (0) | 2024.03.25 |
| [ 백준 BOJ ] 20303 번 - 할로윈의 양아치 (C++) (0) | 2024.03.23 |
| [백준 BOJ] 16724번 - 피리 부는 사나이 (C++) (1) | 2024.03.22 |
| [백준 BOJ] 4386번 - 별자리 만들기 (C++) (1) | 2024.03.18 |