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 ..

순차 탐색(Sequential Search) 순차 탐색 어떤 데이터는 정렬되지 않은 상태로 존재하고, 어떤 데이터는 정렬된 상태로 존재한다. 이 두 경우에 데이터를 찾는 방법은 조금 다르다. ① 정렬되지 않은 집합에서의 순차 탐색 검색 성공 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다. 검색 실패 첫 번째 데이터부터 차례로 비교해서 찾지 못할 경우, -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다. def seqSearch(ary, fData) : pos = -1 size = len(ary) print('## 비교한 데이터 ==> ', end = '') for i in range(size) : print(ary[i], end = ' ') if ary[i] == fData..