lower_bound() (1) 썸네일형 리스트형 이분탐색 (binary search) C++ STL 사용법 알아보고, 구현해보자! 1. 정의 살펴보기 오늘은 이분 탐색 알고리즘에 대해서 알아보겠다. 여느 때와 동일하게 위키피디아를 켰다. 장황하게 설명되어 있는데, 핵심 문장을 살펴보면 아래와 같다. 타겟 밸류와 배열의 중간값을 비교하여 일치하지 않았다면 '타겟이 있을 수 없는 절반의 영역을 삭제' 한 후, 나머지 절반의 영역에서 해당 과정을 반복하는 탐색방법이다. 이 탐색은 타겟이 발견될 때까지 계속된다. 라고 되어있다. 요컨데, 내가 초등학생 때 했던 놀이 중 하나와 상당히 닮아 있는 것 같다. 혹시 Up Down 게임을 해 봤다면 이해가 굉장히 쉬울 것 같다. 1부터 100까지의 숫자를 하나 생각하고, 상대가 하나를 추측해서 제시한다. 그럼 나는 내가 생각한 숫자가 더 크다면 UP, 내가 생각한 숫자가 더 작다면 DOWN을 외치.. 이전 1 다음
