이진탐색
- 정의: 정렬된 배열에서 값을 찾는 탐색 알고리즘
- 핵심
- 반드시 정렬된 배열에서 수행해야한다. (sort()사용)- 탐색 범위를 절반씩 줄여나가며 값을 찾는다
- 시간 복잡도: O(logn)
bisect 모듈
- 이진탐색을 구현한 파이썬 표준 라이브러리이다.
bisect_left(arr, x): 정렬된 arr에 x를 삽입할 가장 왼쪽 위치를 반환(맨 처음 x의 인덱스)bisect_right(arr, x): 정렬된 arr에 x를 삽입할 가장 오른쪽 위치를 반환(마지막 x의 바로 다음 인덱스)bisect_insort_left(arr, x): x를 정렬 순서에 맞게 삽입
활용 예:
- x가 arr에 있는지 확인:
bisect_left(arr, x)이 반환한 위치의 값이 x와 같은지 확인 - x가 몇개 있는지 확인:
bisect_right(arr, x) - bisect_left(arr, x)
자주 나오는 변형: 파라메트릭 서치(Parametric Search)
단순히 값(value)을 찾는 것이 아니라, "특정 조건을 만족하는 최적의 값(예: 최소/최대 값)"을 이진 탐색으로 찾는 문제
- 탐색 대상: 값이 아니라 '답이 될 수 있는 범위' (ex. 0부터 10^9 까지)
