이진 탐색과 Lower/Upper Bound
정렬된 배열의 탐색 구간을 절반씩 줄여 값과 중복 구간의 경계를 찾는 방법
알고리즘 복잡도
개요
이진 탐색(Binary Search)은 정렬된 배열에서 가운데 값을 확인한 뒤, 답이 있을 수 없는 절반을 버리는 탐색 알고리즘입니다. 일반 이진 탐색이 목표값과 같은 원소 하나를 찾는다면, Lower Bound와 Upper Bound는 중복된 값의 시작과 끝 경계를 찾습니다.
반열린 탐색 구간 `[low, high)`
- 포함 범위:
low는 현재 후보에 포함되고high는 포함되지 않습니다. - 중간 위치:
mid = low + Math.floor((high - low) / 2)로 계산합니다. - 핵심 불변식: 정답이 존재한다면 매 단계의 후보 구간
[low, high)안에 남아 있습니다. - 종료 조건:
low === high가 되면 더 나눌 후보가 없으며, 그 위치가 경계 탐색의 결과가 됩니다.
일반 이진 탐색
values[mid] === target이면 즉시 성공합니다. 중복값이 있으면 그중 어느 위치든 반환할 수 있으므로 첫 번째 또는 마지막 위치를 보장하지 않습니다. 값이 더 작으면 왼쪽 절반과 mid를 버리고, 더 크면 오른쪽 절반과 mid를 버립니다.
Lower Bound와 Upper Bound
- Lower Bound:
target이상인 값이 처음 나타나는 위치입니다.values[mid] < target일 때만low를 오른쪽으로 옮기고, 같아도 더 앞쪽 경계를 찾기 위해high = mid로 줄입니다. - Upper Bound:
target보다 큰 값이 처음 나타나는 위치입니다.values[mid] <= target이면 같은 값까지 건너뛰도록low = mid + 1로 옮깁니다. - 중복 개수: 정렬 배열에서 목표값의 개수는
upperBound(target) - lowerBound(target)입니다.
값이 없거나 배열 끝에 있는 경계
Lower Bound와 Upper Bound는 목표값이 없어도 삽입 위치를 반환합니다. 모든 원소가 조건을 만족하지 않으면 배열 길이 n을 반환할 수 있으므로, 시각화의 high와 결과 포인터는 마지막 원소 다음 칸까지 이동합니다.
실행 예제로 확인하기
정렬된 배열 [1, 2, 2, 2, 4]에서 target=2라면 lower bound는 인덱스 1, upper bound는 인덱스 4입니다. 따라서 등장 횟수는 4-1=3개입니다. target=5라면 두 경계 모두 배열의 길이 5를 반환합니다.
학습 목표
- 반열린 구간에서 lower/upper bound의 결과를 직접 계산할 수 있다.
자주 하는 오해
- Upper Bound는 목표값의 마지막 인덱스가 아니라 목표값보다 큰 첫 위치입니다.
핵심 정리
- 중복 개수는 upperBound(target) - lowerBound(target)으로 계산합니다.
학습 확인
핵심 단계
- 1
정렬된 배열 전체를 반열린 후보 구간 [low, high)로 설정
- 2
가운데 인덱스 mid를 계산하고 values[mid]와 target을 비교
- 3
선택한 모드의 비교 조건에 따라 low 또는 high를 갱신하여 후보 구간을 절반으로 축소
- 4
일반 탐색은 일치 시 종료하고, 경계 탐색은 low와 high가 만날 때까지 반복
- 5
lower bound와 upper bound의 차이로 목표값의 중복 개수를 계산
핵심 개념 및 실무 적용 분야
참고 자료
개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.