수백만 개의 정렬된 데이터 속에서 원하는 값을 찾아낼 때 O(log N)의 압도적인 속도를 보여주는 이분 탐색(Binary Search). 하지만 실무 시스템 구축이나 코딩 테스트에서 이분 탐색을 맹목적으로 적용하다 보면 전혀 예상치 못한 치명적인 함정에 빠지게 됩니다. 바로 "찾고자 하는 타겟 데이터가 배열 내에 여러 개 중복되어 존재할 때"입니다. 기본 이분 탐색 코드는 중복된 값들 중 어느 위치에 있는 값을 반환할지 전혀 보장하지 않으며, 그저 운 좋게 걸린 '아무거나' 하나를 찾아내고 쿨하게 탐색을 종료해 버립니다. 만약 "80점을 받은 학생들이 배열에 총 몇 명인가?" 또는 "새로운 80점짜리 데이터를 끼워 넣을 수 있는 가장 앞쪽 위치는 어디인가?"를 구해야 한다면 기본 이분 탐색은 완벽한 무용지물이 됩니다. 이 완벽해 보이는 알고리즘의 결함을 메우고 활용도를 극대화하기 위해 탄생한 심화 개념이 바로 Lower Bound(하한선)와 Upper Bound(상한선)입니다.
1. 중복 데이터가 낳은 이분 탐색의 한계
오름차순으로 정렬된 배열 [1, 2, 2, 2, 2, 4, 5]가 있습니다. 여기서 타겟 숫자 2를 기본 이분 탐색으로 찾는다고 가정해 봅시다. 중간값(Mid)을 딱 쪼갰을 때 우연히 3번 인덱스에 있는 2를 짚었다면 알고리즘은 "찾았다!" 하고 곧바로 인덱스 3을 반환하며 종료해 버립니다. 하지만 우리 시스템에 필요한 값이 '2가 처음 시작되는 1번 인덱스'이거나 '2가 완전히 끝나는 지점 다음인 5번 인덱스'라면 어떨까요? 이 문제를 해결하기 위해 이분 탐색의 탈출 조건(return)을 교묘하게 비틀어버린 것이 바로 Bound 탐색 기법입니다.
2. Lower Bound (하한선): 타겟 이상의 값이 최초로 나오는 위치
Lower Bound는 "찾고자 하는 타겟 값과 같거나, 타겟보다 큰 값이 처음으로 등장하는 인덱스"를 찾는 알고리즘입니다.
2-1. 구현의 핵심 로직
기본 이분 탐색은 arr[mid] == target일 때 바로 정답을 리턴하고 탈출합니다. 하지만 Lower Bound는 타겟을 찾았더라도 절대 만족하지 않고 "아니야, 네 앞쪽(왼쪽)에 똑같은 타겟이 더 있을지도 몰라!"라며 탐색 범위를 왼쪽으로 강제로 좁혀버립니다(high = mid). 오직 범위가 한 칸으로 좁혀져 low와 high가 겹치는 순간이 되어서야 그 자리를 리턴합니다.
// Lower Bound 코드 구현 (Java 예시)
int lowerBound(int[] arr, int target) {
int low = 0;
int high = arr.length; // 배열의 끝 인덱스(length-1)가 아니라 길이(length)를 잡는 것에 극도로 주의해야 합니다!
while (low < high) {
int mid = (low + high) / 2;
// 타겟과 같거나 크면, 혹시 왼쪽에 타겟이 더 있는지 찾아보기 위해 high를 당김
if (arr[mid] >= target) {
high = mid;
} else {
low = mid + 1; // 타겟보다 작으면 무조건 오른쪽 탐색
}
}
return low; // 최초로 등장하는 하한선 인덱스 반환
}
3. Upper Bound (상한선): 타겟을 초과하는 값이 최초로 나오는 위치
Upper Bound는 "찾고자 하는 타겟 값을 '초과'하는(명백히 더 큰) 값이 처음으로 등장하는 인덱스"를 찾는 알고리즘입니다.
3-1. 구현의 핵심 로직
이번에는 arr[mid]가 타겟과 같을 때의 행동이 다릅니다. 타겟을 찾았어도 "나는 너보다 확실히 큰 값을 원해. 그러니까 타겟과 같은 값이 나오면 뒤도 돌아보지 말고 무조건 오른쪽(뒷부분)으로 더 넘어가자!"라며 low를 오른쪽으로 밀어버립니다(low = mid + 1). 이렇게 타겟과 같은 무리들을 전부 뚫고 지나가 최초로 더 큰 값이 나오는 경계선을 정확히 찾아냅니다.
// Upper Bound 코드 구현 (Java 예시)
int upperBound(int[] arr, int target) {
int low = 0;
int high = arr.length;
while (low < high) {
int mid = (low + high) / 2;
// 타겟값 이하의 숫자라면, 타겟을 완벽히 초과하는 값을 찾기 위해 low를 오른쪽으로 밈
if (arr[mid] <= target) {
low = mid + 1;
} else {
high = mid; // 타겟보다 크다면, 거기가 상한선일 수 있으므로 high를 당김
}
}
return low;
}
4. 두 기법의 융합: 특정 범위 내의 데이터 개수 구하기
이 두 가지 기법을 마스터하면 엄청난 활용도를 자랑합니다. 앞선 배열 [1, 2, 2, 2, 2, 4, 5]에서 숫자 2가 총 몇 개인지 구하고 싶다면 어떻게 할까요?
순차 탐색으로 하나씩 세면 O(N)이 걸리지만, Upper Bound 인덱스(5) - Lower Bound 인덱스(1) = 4개라는 공식을 사용하면 O(log N)의 압도적인 속도로 중복 데이터의 개수를 단숨에 도출해 낼 수 있습니다. 이 기법은 데이터베이스 인덱싱이나 대규모 로그 분석에서 빈번하게 사용되는 핵심 기술입니다.
1. 기본 이분 탐색은 중복된 데이터가 존재할 때 어떤 위치의 값을 반환할지 보장하지 못하는 치명적인 한계가 있습니다.
2. Lower Bound(하한선)는 타겟 이상이 처음 나오는 위치를, Upper Bound(상한선)는 타겟을 초과하는 값이 처음 나오는 위치를 찾아냅니다.
3. 이 두 가지 결괏값을 서로 빼면(Upper - Lower) 특정 숫자가 배열 내에 몇 개 존재하는지 O(log N)의 고속으로 알아낼 수 있습니다.