이진탐색 바운드
-
Binary Search 이진탐색(2) Lower/Upper boundAlgorithm/Theory 2020. 6. 12. 15:07
이진탐색이 정확히 원하는 값을 찾는 거라면, lower/upper bound는 원하는 값보다 처음으로 크거나 작은 값이 나오는 위치를 찾는 방법으로 중복된 요소나 타겟의 상한 하한을 찾는 경우 등 다양한 방식으로 활용될 수 있습니다. 이진 탐색에서 약간의 변형이 들어간 것으로 이진탐색을 이해하셨다면 어렵지 않게 이해할 수 있습니다. 이진탐색이 궁금하다면? --> 여기로 코드를 보기 전에 lower와 upper의 차이를 간략하게 정리해보고 가겠습니다. lower bound는 타겟보다 같거나 큰 값이 나오는 처음 위치를 찾습니다. upper bound는 타겟보다 처음으로 큰 값이 나오는 위치를 찾습니다. [1, 2, 2, 3, 3, 3, 4, 6] LowerBound(3) --> 3 UpperBound(3)..