이진 탐색
이미 정렬되어 있는 데이터에서 특정 데이터를 찾기 위해, 탐색 범위를 계속 절반으로 나눠 탐색하는 알고리즘
이진 탐색은 배열에서 특정 데이터를 탐색하기 위한 알고리즘이다. 배열의 모든 원소를 탐색하면서 $O(N)$의 시간복잡도로 원하는 데이터를 찾는 선형 탐색과는 다르게, 한 번 탐색할 때마다 범위를 절반으로 줄여가면서 탐색하므로 $O(\log N)$의 시간복잡도를 갖게 된다. 그러나, 이진 탐색은 반드시 정렬된 배열에서만 사용할 수 있으므로, 정렬되지 않은 데이터에 대해서는 정렬을 하기 위한 시간복잡도가 추가로 필요하게 된다. 해당 링크에서 선형 탐색과 이진 탐색의 시각적인 동작에 대해서 확인할 수 있다.
이진 탐색은 변수 3개를 이용해서 수행한다. 탐색 범위의 시작을 나타내는 start, 탐색 범위의 끝을 나타내는 end, 그리고 탐색 범위의 중간점을 나타내는 mid 변수를 이용한다. 이를 이용한 이진 탐색 방법은 다음과 같다.
- 오름차순으로 정렬된 배열의 제일 시작점을
start, 끝 점을end로 두고,mid = (start + end) / 2로 정의한다. - 찾으려고 하는 값을
target이라고 했을 때,target과mid위치에 존재하는 값의 대소를 비교한다. - 만약,
target < arr[mid]라면,mid왼쪽에target데이터가 존재하는 것으로 생각할 수 있다. 따라서,end = mid - 1로 설정한다. - 만약,
target > arr[mid]라면,mid오른쪽에target데이터가 존재하는 것으로 생각할 수 있다. 따라서,start = mid + 1로 설정한다. - 2~4의 과정을 반복하다가,
target == arr[mid]가 되는 순간 탐색을 종료한다. - 만약
end < start가 된다면, 찾고자 하는 데이터가 배열에 존재하지 않는다고 볼 수 있다.
Python으로 구현한 이진 탐색의 코드는 아래와 같다.
def binary_search(num_list: List[int], target: int) -> int:
"""
Args:
num_list: 오름차순으로 정렬된 숫자의 배열
target: 찾고자 하는 데이터
Return:
int: target이 위치하는 인덱스, 존재하지 않는다면 -1
"""
start = 0
end = len(num_list)-1
while start <= end:
mid = (start + end) // 2
if target < num_list[mid]:
end = mid - 1
elif target > num_list[mid]:
start = mid + 1
else:
return mid
return -1
이진 탐색 주의사항
- 반드시 배열이 정렬되어 있어야 한다: 알고리즘이
target의 위치에 기반해 동작하므로, 오름차순 or 내림차순으로 반드시 배열이 정렬되어야 한다. 만약, 내림차순 정렬이라면 위의 3번과 4번 과정을 신경써주면 된다. - 무한루프에 빠지지 않게
mid값을 정해야 한다: 만약 구간이 정확히 절반으로 나누어지지 않는 경우, 문제에 따라 무한루프에 빠질 수 있다. Lower Bound나 Upper Bound 탐색 문제에서 이 문제를 더욱 신경써야 한다.
Lower Bound & Upper Bound
일반적인 이진 탐색은 찾고자 하는 값이 없다면, 그대로 탐색에 실패하게 된다. 그러나, Lower Bound나 Upper Bound와 같은 문제는 이와 상관없이 찾고자 하는 값 이상/초과의 위치를 탐색하게 된다. 이는 탐색하고자 하는 값이 없는 경우나, 동일한 값이 여러 개 들어있는 경우 모두에서 사용가능하다.
Lower Bound
찾고자 하는 값 이상이 처음 나타나는 위치를 탐색
즉, 위에서는 target == arr[mid] 인 mid 값을 찾았다면, Lower Bound 문제는 target > arr[mid - 1]이면서 target <= arr[mid] 를 만족하는 mid 값을 찾는 것이 목표이다.
e.g.) 10, 13, 15, 15, 17, 17, 19 에서 15의 Lower Bound는 15가 처음 등장하는 위치
만약, 배열에 들어있는 모든 값들이 target 보다 작다면, “배열의 마지막 인덱스 + 1”의 값을 반환한다.
Python으로 구현하면 다음과 같다.
def lower_bound(num_list: List[int], target: int) -> int:
"""
Args:
num_list: 오름차순으로 정렬된 숫자의 배열
target: 찾고자 하는 데이터
Return:
int: target 이상의 값이 처음으로 등장하는 인덱스
"""
start = 0
end = len(num_list)
while start < end:
mid = (start + end) // 2
if target <= num_list[mid]:
end = mid
elif target > num_list[mid]:
start = mid + 1
return end
Upper Bound
찾고자 하는 값보다 큰 값이 처음 나타나는 위치를 탐색
Lower Bound는 찾고자 하는 값인 target을 탐색 범위에 포함했다면, Upper Bound는 찾고자 하는 값보다 큰 값이 처음 등장하는 위치를 탐색하는 것이다. 즉, target >= arr[mid - 1]이면서 target < arr[mid] 를 만족하는 mid 값을 찾는 것이 목표이다.
e.g.) 10, 13, 15, 15, 17, 17, 19 에서 15의 Upper Bound는 15가 마지막으로 등장하는 위치 + 1
Upper Bound도 마찬가지로, 배열에 들어있는 모든 값들이 target 보다 작다면, “배열의 마지막 인덱스 + 1”의 값을 반환한다.
Python으로 구현하면 다음과 같다.
def upper_bound(num_list: List[int], target: int) -> int:
"""
Args:
num_list: 오름차순으로 정렬된 숫자의 배열
target: 찾고자 하는 데이터
Return:
int: target보다 큰 값이 처음으로 등장하는 인덱스
"""
start = 0
end = len(num_list)
while start < end:
mid = (start + end) // 2
if target < num_list[mid]:
end = mid
elif target >= num_list[mid]:
start = mid + 1
return end
동일한 값의 개수 찾기
위의 Lower Bound & Upper Bound를 이용해서, 정렬된 배열 내에서 동일한 값이 몇 개 존재하는지를 빠르게 계산할 수 있다.
Upper Bound는 찾는 값보다 큰 값이 처음 등장한 위치를 탐색하고, Lower Bound는 찾는 값 이상의 값이 처음 등장한 위치를 탐색하므로, "Upper Bound 값 - Lower Bound 값"이 찾고자 하는 값의 등장 횟수가 된다. 만약 이 값이 0이면, 해당 배열에 찾는 값이 존재하지 않는 경우로 생각할 수 있다.
References
'Algorithm > 개념 정리' 카테고리의 다른 글
| 이진 탐색 트리 (Binary Search Tree) (1) | 2026.04.28 |
|---|---|
| 투 포인터 (Two Pointers) (1) | 2026.04.22 |
| 그리디 알고리즘 (Greedy Algorithm) (0) | 2026.04.22 |
| 다이나믹 프로그래밍 (Dynamic Programming) (0) | 2026.04.14 |
| 백트래킹 (Backtracking) (0) | 2026.04.14 |