[Algorithm] 이분 탐색 - 심화
2025. 1. 21. 16:01
CS/Algorithm
이분 탐색을 활용한 Parametric Search 문제에서 정말 다양한 코드들이 존재한다. 우선 종료 조건에 따라, st 과 st 으로 분리된다. 또한, 구간 업데이트 시, st = mid + 1, st = mid 혹은 en = mid - 1, en = mid 과 같은 다양한 코드들을 마주하게 된다.이들의 조합을 생각해 보면 정말 수많은 조합이 가능해진다. 실제로 PS에서 이런 종료 조건들에 의해 답이 틀리는 경우도 있었으며, 무한 루프에 빠지는 경험을 자주 하곤 했다. 이에 따라 이들의 차이점에 대해 정리하고자 한다.아래의 나오는 코드들은 Swift로 작성되었다. 이분 탐색"이분 탐색"은 정렬되어 있는 원소들에서 탐색 범위를 절반으로 줄여가며 탐색하는 알고리즘이다.func binarySearch..