버그 없는 고전적인 이진 탐색
low, high, mid 반복문을 정확히 작성합니다
버그 없는 고전적인 이진 탐색은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
탐색 범위를 절반으로 줄이세요
이진 탐색은 정렬된 리스트에서 매 단계마다 범위를 절반으로 줄여 값을 찾습니다. 따라서 느린 O(n) 탐색이 빠른 O(log n) 탐색으로 바뀝니다.
a = [1, 3, 5, 7, 9] # must be sorted정렬이 유일한 규칙입니다
이진 탐색은 정렬된 데이터에서만 작동합니다. 리스트가 정렬되지 않았다면 먼저 정렬하세요. 그렇지 않으면 결과가 의미 없고 틀립니다.
a.sort() # ascending order required두 경계
두 포인터로 시작하세요. low는 인덱스 0에, high는 마지막 인덱스에 둡니다. 대상 값이 있다면 항상 그 사이에 있습니다.
low, high = 0, len(a) - 1중간을 안전하게 찾으세요
mid를 low + (high - low) // 2로 계산하세요. Python에서는 오버플로가 문제가 되지 않지만, 이 형식은 어디서나 안전한 습관입니다.
mid = low + (high - low) // 2세 가지 결과
a[mid]를 대상 값과 비교하세요. 찾았거나, 너무 작거나, 너무 큽니다. 각 경우에 범위를 서로 다르게 줄입니다.
if a[mid] == target:
return mid너무 작으면 오른쪽으로 이동하세요
a[mid]가 대상 값보다 작다면 답은 오른쪽에 있어야 합니다. low를 mid + 1로 옮겨 왼쪽 절반을 버리세요.
elif a[mid] < target:
low = mid + 1너무 크면 왼쪽으로 이동하세요
a[mid]가 대상 값보다 크다면 왼쪽 절반을 탐색하세요. high를 mid - 1로 옮기면 mid를 다시 확인하지 않습니다.
else:
high = mid - 1반복 조건
low가 high보다 작거나 같은 동안 계속하세요. 두 값이 교차하면 범위가 비어 있고 대상 값이 없는 것입니다.
while low <= high:
mid = low + (high - low) // 2찾지 못했다고 알리세요
일치하는 값을 찾지 못한 채 반복이 끝나면 해당 값은 없습니다. 호출하는 쪽에서 성공과 실패를 구분할 수 있도록 관례에 따라 -1을 반환하세요.
return -1 # target not in list오프바이원 함정
가장 흔한 버그는 포인터를 옮길 때 +1 또는 -1을 잊는 것입니다. 이를 생략하면 mid가 영원히 다시 검사되어 무한 반복이 발생합니다.
low = mid + 1 # not low = mid가능하면 라이브러리를 사용하세요
단순한 포함 여부 검사라면 Python의 bisect 모듈에 이미 버그 없는 탐색이 있습니다. 사용자 지정 로직이 필요할 때만 반복문을 직접 작성하세요.
import bisect
i = bisect.bisect_left(a, target)빠른 확인
반복이 올바르게 진행되도록 만드는 요소를 생각해 보세요.
복습: 버그 없는 탐색
이제 low와 high를 설정하고, mid를 안전하게 계산하며, 올바른 쪽을 줄이고, 오프바이원 함정을 피할 수 있습니다. 로그 시간 탐색을 익혔습니다. 🎯
자주 묻는 질문
“버그 없는 고전적인 이진 탐색” 강의는 무료인가요?
네 — “버그 없는 고전적인 이진 탐색” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“버그 없는 고전적인 이진 탐색”에서 뭘 배우나요?
low, high, mid 반복문을 정확히 작성합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“버그 없는 고전적인 이진 탐색” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 버그 없는 고전적인 이진 탐색
- bisect_left와 bisect_right
- 첫 번째 True: 술어 이진 탐색
- 정답에 대한 이진 탐색