이분탐색의 올바른 사고방식 익히고 lower_bound, upper_bound 가볍게 복기하기

1. 이분 탐색(binary search) False 구간, True 구간 2개의 partition으로 분할된 구간에서, 분할 경계의 위치를 O(logN)에 찾는 알고리즘이다. STL로 구현된 lower_bound와 upper_bound는 가장 유명한 이분 탐색 함수중 하나이다. 정렬된 배열에서 x의 lower bound는 정렬 상태를 유지한 채 x를 삽입할 수 있는 첫번째 위치이고 upper_bound는 마지막 위치이다. 위 그림에서 lower_bound(20)은 20을 넣을 수 있는 첫번째 위치로, 1번에 넣을 수 있다.. upper_bound(20)은 20을 넣을 수 있는 마지막 위치로, 4번에 넣을 수 있다..(원래 4번은 5번으로 이동하겠지) 이분 탐색적 설명으로는, lower_bound는 x보..