Per ardua ad astra.

lower_bound(), upper_bound() ; 이진 탐색(Binary Search) 소개이진 탐색(Binary Search)으로 원소를 탐색하는 함수시간 복잡도가 $O(\log_{2} N)$ 으로, 빠른 속도로 탐색을 수행할 수 있다.탐색을 진행할 컨테이너는 반드시 오름차순으로 정렬되어 있어야 한다. 필요한 헤더#include  형식찾은 값(val)의 주소를 Iterator 형으로 반환한다.lower_bound(ForwardIterator first, ForwardIterator last, const T& val)lower_bound(ForwardIterator first, ForwardIterator last, const T& val) lower_bound()찾으려는 키 값보다 크거나 같은(이..

이진 탐색(Binary Search) 이진 탐색 원리 정렬된 데이터 집합을 검색하는 경우에는 이진 탐색(Binary Search)을 주로 사용하는데, 순차 탐색에 비해서 엄청난 성능으로 데이터를 검색할 수 있다. 이진 탐색은 전체를 반씩 잘라내서 한쪽을 버리는 방식을 사용한다. 데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다. 찾는 값을 검색하고자 1단계에서 중앙 위치를 기준으로 잡는다. 찾는 값이 왼쪽 구역에 있을 경우, 오른쪽 구역을 버린다. 이 과정을 찾을 값을 찾을 때까지 반복한다. 구현 이진 탐색 구현은 키를 찾기 위해 계속 시작, 중앙, 끝을 반복적으로 1/2씩 줄여 가면서 계산하는 방식이다. 검색할 범위를 1/2씩 반복해서 분할하는 기법을 분할 정복(Divide ..