Binary search
이진 탐색
중간값을 보고 범위를 절반으로 줄여요
정렬된 배열에서 17을 찾아요
왼쪽 left0
오른쪽 right6
찾는 값17
현재 위치비교 대상확인한 값
예제 코드
C++
<vector>int binary_search(const std::vector<int>& a, int target) { int left = 0; int right = static_cast<int>(a.size()) - 1; while (left <= right) { int mid = left + (right - left) / 2; if (a[mid] == target) return mid; if (a[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;}Python
def binary_search(a, target): left, right = 0, len(a) - 1 while left <= right: mid = left + (right - left) // 2 if a[mid] == target: return mid if a[mid] < target: left = mid + 1 else: right = mid - 1 return -1시작하기
탐색 범위를 정해요
정렬된 배열에서 17을 찾아요. 양 끝을 포함한 [left, right]가 아직 확인할 범위예요.
사용 조건
오름차순으로 정렬된 배열에서 값을 찾을 때 사용해요. 정렬 덕분에 확인하지 않아도 될 절반을 제외할 수 있어요.
먼저 알아두면 좋아요
배열, 인덱스, 조건문을 알고 시작해요. 이 예제는 양 끝을 포함하는 [left, right] 범위를 사용해요.
동작 원리
중간 인덱스를 계산하고 그 위치의 값을 비교해요. 찾는 값이 더 크면 왼쪽 절반을, 더 작으면 오른쪽 절반을 제외해요.
비교한 중간값도 다음 범위에서 제외해요. left가 right보다 커지면 남은 범위가 없어 탐색이 끝나요. 중복된 값의 첫 위치를 찾는 문제는 경계 처리를 따로 바꿔야 해요.
- 시간
- O(log n) · 매번 남은 범위를 절반으로 줄여요
- 추가 공간
- O(1) · 세 인덱스로 범위를 관리해요
주의할 점
- 정렬되지 않은 배열에 바로 사용하면 올바른 범위를 버릴 수 있어요.
- left = mid + 1, right = mid − 1로 범위를 줄여요. 중간값을 남기면 반복이 끝나지 않을 수 있어요.