•
정렬된 배열에서 특정 값을 빠르게 찾기 위한 알고리즘
•
시간복잡도 : O(logN)
개념 & 기본 흐름
개념
•
전제 조건 : 배열이 정렬되어 있을 것
•
방식 : 중간 값을 기준으로 탐색 범위를 절반으로 줄여나감
기본 흐름
1.
start = 0, end = 배열길이 - 1, mid = [(start + end) // 2]
2.
중간값(arr[mid])과 찾고자 하는 값(target)을 비교:
a.
arr[mid] == target : 찾음
b.
arr[mid] < target : 오른쪽 구간 탐색(start = mid + 1)
c.
arr[mid] > target : 왼쪽 구간 탐색 (end = mid - 1)
핵심 소스코드
반복문
# 전제조건 : 정렬된 배열
def binary_search(arr, target):
start, end = 0, (len(arr) -1)
while start <= end:
mid = (start + end) // 2
if arr[mid] == target:
return arr[mid]
elif arr[mid] > target:
end = mid - 1
else:
start = mid + 1
return -1 # 못 찾은 경우
Python
복사
재귀
def recursive_binary_search(arr, target, start, end):
if start > end:
return -1 # 못 찾은 경우
mid = (start + end) // 2
mid_value = arr[mid]
if mid_value == target:
return mid_value
if mid_value > target:
return recursive_binary_search(arr, target, start, mid - 1)
else:
return recursive_binary_search(arr, target, mid + 1)
Python
복사
이분탐색 개념을 응용한 함수
lower_bound 함수
a = [1, 2, 4, 4, 4, 7, 9]
target = 4
# target보다 크거나 같은 값이 처음 등장하는 인덱스를 찾는 함수
def lower_bound(arr, target):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
# 목적 : arr[i] >= target이 처음으로 참이 되는 i 찾기
if arr[mid] < target:
# 이 경우에는 중앙값이 정답이 아니므로 left = mid+1
left = mid + 1
else:
# arr[mid] > target 경우 : mid값이 답일 수도 있으므로 right = mid(mid - 1 아님)
right = mid
return left
Python
복사
upper_bound 함수
a = [1, 2, 4, 4, 4, 7, 9]
target = 4
# target보다 큰 값이 처음 등장하는 인덱스를 찾는 함수
def upper_bound(arr, target):
left, right = 0, len(arr) - 1
while left < right:
mid = (left + right) // 2
# 목적 : arr[i] > target이 처음으로 참이 되는 i 찾기
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
Python
복사
bisect 모듈
정렬된 리스트에서 이진탐색으로 원소를 삽입할 위치나 특정 값을 빠르게 찾을 수 있도록 도와주는 도구입니다. 기본적으로 정렬된 리스트를 대상으로 동작하며, 숫자 리스트 뿐만 아니라 튜플 리스트도 다룰 수 있습니다.
기본 사용법
import bisect
arr = [1, 3, 3, 5, 7]
bisect.bisect_left(arr, 3) # 1: 가장 왼쪽 3의 위치
bisect.bisect_right(arr, 3) # 3: 가장 오른쪽 3 바로 뒤
bisect.insort(arr, 4) # [1, 3, 3, 4, 5, 7]: 4를 정렬 유지하며 삽입
Python
복사
•
bisect_left(arr, x) : x를 삽입할 가장 왼쪽 인덱스 반환
•
bisect_right(arr, x) : x를 삽입할 가장 오른쪽 인덱스 반환
•
bisect.insort(arr, x) : 정렬된 arr에 x를 정렬 유지하며 삽입
# 예시
import bisect
arr = [1, 3, 3, 5, 7]
bisect_left_index = bisect.bisect_left(arr, 3)
bisect_right_index = bisect.bisect_right(arr, 3)
print("bisect_left:", bisect_left_index) # 👉 1 (3이 처음 나오는 위치)
print("bisect_right:", bisect_right_index) # 👉 3 (3보다 큰 값(5)이 처음 나오는 위치)
# 그렇다면? 3의 개수는? (bisect_right_index - bisect_left_index)라고 할 수 있다!
Python
복사
튜플 리스트에서 특정 원소를 기준으로 이분탐색하려는 경우
import bisect
# 튜플의 첫 번째 값을 기준으로 정렬된 리스트
data = [(1, 'a'), (3, 'b'), (5, 'c'), (7, 'd'), (9, 'e')]
# 찾고 싶은 기준값
target = 6
# target보다 크거나 같은 첫 인덱스 (왼쪽 경계)
index = bisect.bisect_left(data, (target, )
print(f"bisect_left index: {index}") # 결과 : 3
print(f"해당 위치 튜플: {data[index] if index < len(data) else '없음'}")
Python
복사