이분탐색
TL;DR#
- 정렬된 리스트 보다는 주어진 검색결과 (혹은 함숫값)가 True, False 구간으로 나뉘어있을 때 그 경계를 찾는 문제라고 보는 게 더 낫다.
- 그러면 lower_bound 문제는 \(v \ge x\) 를 만족하는 첫번째 v를 찾는 문제가 되고
-
upper_bound 문제는 \(v \gt x\)를 만족하는 첫번째 v를 찾는 문제가 된다.
-
정렬된 배열에서 x의 lower_bound는 정렬 상태를 유지한 채 x를 삽입할 수 있는 첫 번째 위치이며, upper_bound는 마지막 위치입니다.
- 이분 탐색적인 설명으로는, lower_bound는 x보다 크거나 같은 원소의 첫 번째 위치고 upper_bound는 x보다 큰 원소의 첫 번째 위치입니다.
관련 문제#
- 영어 공부
- 3차원 농부
- 백준-1939-중량제한 이분탐색 + BFS로, 어떤 무게 W로 물건을 배달할 수 있는지 여부를 검사한다. 이때 A -> B로 가는 경로를 찾기 위해 BFS를 사용한다.