이분탐색

• 알고리즘
• binary search를 활용한 lower upper bound 그리고 parametric search까지 {Notion export}
• 노션 링크

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를 사용한다.