[이분탐색] Upper / Lower Bound

이분(이진)탐색에서 항상 헷갈리던 Upper / Lower Bound 에 대해서 복습하자.feat. (백준 14003, 소프티어 3307의 LIS 문제를 해결하며.)개요 이분 탐색은 정렬된 요소중 찾고 싶은 값, target(key)을 빠르게 찾는 방법이다. O(logN) 단순히 타겟을 찾는 것을 넘어서, 이진 탐색의 원리를 확장하여 ‘Upper Bound’와 ‘Lower Bound’ 개념을 적용함으로써, 데이터 집합 내에서 특정 값의 범위를 정확하고 빠르게 찾을 수 있어야한다.개념 비교하기 Upper Bound는 주어진 값보다 큰 첫 번째 요소를 찾는다. Lower Bound는 주어진 값 이상의 첫 번째 요소를 찾는다. idx012345678value112223334 찾고 싶은 value, 즉 targ..

2024.07.24