bisect_left와 bisect_right
정렬된 리스트에서 삽입 위치를 찾습니다
bisect_left와 bisect_right은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
반복 코드 없이 탐색하세요
Python의 bisect 모듈은 정렬된 리스트를 위한 검증된 이진 탐색을 제공합니다. 직접 작성한 반복문이 없으므로 오프바이원 버그를 디버깅할 필요도 없습니다.
import bisect삽입 위치이지 불리언이 아닙니다
bisect는 참이나 거짓 대신, 리스트의 정렬을 유지하면서 값을 삽입할 수 있는 인덱스를 반환합니다. 진정한 강점은 바로 이 인덱스입니다.
a = [1, 3, 3, 3, 7]bisect_left는 왼쪽을 선택합니다
bisect_left는 값을 넣을 수 있는 첫 위치를 반환합니다. 중복 값이 있으면 같은 값들보다 앞에 놓이며, 뒤에 놓이는 일은 없습니다.
bisect.bisect_left(a, 3) # 1bisect_right는 오른쪽을 선택합니다
bisect_right는 같은 값이 마지막으로 나온 위치 바로 다음 위치를 반환합니다. 중복 값이 있으면 일치하는 모든 값 뒤에 놓입니다.
bisect.bisect_right(a, 3) # 4같은 값을 가진 원소를 세세요
두 위치를 빼면 O(log n)에 어떤 값의 중복 개수를 셀 수 있습니다. right에서 left를 빼면 해당 값이 나타난 정확한 횟수가 나옵니다.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3값이 존재했을까요?
포함 여부를 확인하려면 bisect_left로 i를 구한 다음 a[i]가 대상 값과 같은지 확인하세요. 먼저 i가 리스트 길이에 도달했는지 검사해야 합니다.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xx 이상인 첫 원소
bisect_left는 x 이상인 첫 원소도 찾습니다. 해당 인덱스가 바로 하한에 해당하는 답을 가리킵니다.
i = bisect.bisect_left(a, x) # first >= x엄격하게 더 큰 첫 원소
x보다 엄격하게 큰 첫 원소가 필요하신가요? bisect_right가 그 인덱스를 바로 반환하며, 이는 상한에 해당합니다.
i = bisect.bisect_right(a, x) # first > x삽입해도 정렬을 유지하세요
insort는 한 번의 호출로 위치를 찾고 삽입하여 리스트를 정렬된 상태로 유지합니다. 정렬된 구조를 즉석에서 만들어 갈 때 유용합니다.
bisect.insort(a, 5) # a stays sorted범위 안에서 탐색하세요
선택적인 lo와 hi 인수로 탐색을 슬라이스로 제한할 수 있습니다. 부분 범위만 필요할 때 복사하지 않아도 됩니다.
bisect.bisect_left(a, x, 2, 5)도우미 리스트로 키를 사용하세요
bisect는 전체 원소를 비교하므로 필드를 기준으로 탐색하려면 해당 키만 담은 병렬 리스트를 만들고 그 리스트에 bisect를 적용하세요.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)빠른 확인
중복 값과 삽입 위치를 기준으로 추론해 보세요.
복습: bisect 완전 정복
이제 삽입 위치를 찾고, 중복을 세며, 로그 시간에 하한과 상한을 찾을 수 있습니다. 반복문을 작성하기 전에 bisect를 먼저 고려하세요. ✨
자주 묻는 질문
“bisect_left와 bisect_right” 강의는 무료인가요?
네 — “bisect_left와 bisect_right” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“bisect_left와 bisect_right”에서 뭘 배우나요?
정렬된 리스트에서 삽입 위치를 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“bisect_left와 bisect_right” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 버그 없는 고전적인 이진 탐색
- bisect_left와 bisect_right
- 첫 번째 True: 술어 이진 탐색
- 정답에 대한 이진 탐색