[C++/STL] 이분탐색

이분탐색은 반드시 이미 정렬되어 있는 배열을 기준으로 한다.

이분탐색의 시간복잡도 : O(logN)

헤더 파일 : #include <algorithm>

---

bool binary_search(<#_ForwardIterator __first#>, <#_ForwardIterator __last#>, <#const _Tp &__value_#>, <#_Compare __comp#>)

:  이분 탐색을 시도 후 있으면 true,  없으면 false 반환.

 

ex )     if(binary_search(v.begin(), v.end(), num)) 이런식으로 벡터안에 num 있는지 체크할 때 유용!

---

Iterator lower_bound(<#_ForwardIterator __first#>, <#_ForwardIterator __last#>, <#const _Tp &__value_#>, <#_Compare __comp#>)

: 찾고자하는 값 이상이 처음 나타나는 곳의 iterator를 반환.

 

iterator 대신 해당 index로 나타내기 원한다면

lower_bound(~~~~) - v.begin()  과 같이 처음 시작 iterator를 빼주면 된다.

---

Iterator upper_bound(<#_ForwardIterator __first#>, <#_ForwardIterator __last#>, <#const _Tp &__value_#>, <#_Compare __comp#>

: 찾고자하는 값 초과 값이 처음 나타나는 곳의 iterator를 반환.

 

iterator 대신 해당 index로 나타내기 원한다면

upper_bound(~~~~) - v.begin()  과 같이 처음 시작 iterator를 빼주면 된다.