728x90
- 반복적(iterative) 방식의 이진 검색 구현
- 재귀적(recursive) 방식의 이진 검색 구현
- 다양한 테스트 케이스를 통한 검증
- 대규모 배열에서 두 방식의 성능 비교
- 선형 검색과 이진 검색의 성능 비교
def binary_search(arr, target):
"""
정렬된 배열에서 타겟 값의 인덱스를 찾는 이진 검색 함수
Args:
arr: 정렬된 리스트
target: 찾으려는 값
Returns:
타겟 값의 인덱스, 없으면 -1
"""
left, right = 0, len(arr) - 1
while left <= right:
# 중간 인덱스 계산
mid = (left + right) // 2
# 타겟을 찾은 경우
if arr[mid] == target:
return mid
# 타겟이 중간 값보다 큰 경우, 오른쪽 부분 탐색
elif arr[mid] < target:
left = mid + 1
# 타겟이 중간 값보다 작은 경우, 왼쪽 부분 탐색
else:
right = mid - 1
# 타겟을 찾지 못한 경우
return -1
# 재귀적 방식의 이진 검색 구현
def binary_search_recursive(arr, target, left=None, right=None):
"""
정렬된 배열에서 타겟 값의 인덱스를 찾는 재귀적 이진 검색 함수
Args:
arr: 정렬된 리스트
target: 찾으려는 값
left: 시작 인덱스
right: 끝 인덱스
Returns:
타겟 값의 인덱스, 없으면 -1
"""
# 초기 호출 시 left와 right가 None이면 초기화
if left is None:
left = 0
if right is None:
right = len(arr) - 1
# 기저 조건: 범위가 유효하지 않은 경우
if left > right:
return -1
# 중간 인덱스 계산
mid = (left + right) // 2
# 타겟을 찾은 경우
if arr[mid] == target:
return mid
# 타겟이 중간 값보다 큰 경우, 오른쪽 부분 재귀 호출
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
# 타겟이 중간 값보다 작은 경우, 왼쪽 부분 재귀 호출
else:
return binary_search_recursive(arr, target, left, mid - 1)
# 테스트 코드
def test_binary_search():
# 테스트 케이스
test_cases = [
{"arr": [1, 2, 3, 4, 5], "target": 3, "expected": 2},
{"arr": [1, 2, 3, 4, 5], "target": 6, "expected": -1},
{"arr": [], "target": 1, "expected": -1},
{"arr": [1], "target": 1, "expected": 0},
{"arr": [1, 3, 5, 7, 9, 11], "target": 7, "expected": 3},
{"arr": [1, 3, 5, 7, 9, 11], "target": 6, "expected": -1},
]
# 반복적 방식 테스트
print("반복적 이진 검색 테스트")
for i, case in enumerate(test_cases):
result = binary_search(case["arr"], case["target"])
if result == case["expected"]:
print(f"테스트 케이스 {i+1} 통과: {case['arr']}, 타겟={case['target']}, 결과={result}")
else:
print(f"테스트 케이스 {i+1} 실패: {case['arr']}, 타겟={case['target']}, 기대값={case['expected']}, 결과={result}")
print("\n재귀적 이진 검색 테스트")
for i, case in enumerate(test_cases):
result = binary_search_recursive(case["arr"], case["target"])
if result == case["expected"]:
print(f"테스트 케이스 {i+1} 통과: {case['arr']}, 타겟={case['target']}, 결과={result}")
else:
print(f"테스트 케이스 {i+1} 실패: {case['arr']}, 타겟={case['target']}, 기대값={case['expected']}, 결과={result}")
# 메인 실행
if __name__ == "__main__":
test_binary_search()
# 추가 예제: 대규모 정렬된 배열에서의 검색 성능 측정
import time
import random
print("\n대규모 배열에서의 성능 테스트")
# 정렬된 대규모 배열 생성
large_array = sorted([random.randint(0, 1000000) for _ in range(1000000)])
# 배열 내에 존재하는 무작위 타겟 선택
target = random.choice(large_array)
# 반복적 방식 성능 측정
start_time = time.time()
result_iterative = binary_search(large_array, target)
end_time = time.time()
print(f"반복적 이진 검색 실행 시간: {end_time - start_time:.6f}초")
print(f"타겟 {target}의 인덱스: {result_iterative}")
# 재귀적 방식 성능 측정
start_time = time.time()
result_recursive = binary_search_recursive(large_array, target)
end_time = time.time()
print(f"재귀적 이진 검색 실행 시간: {end_time - start_time:.6f}초")
print(f"타겟 {target}의 인덱스: {result_recursive}")
# 선형 검색과 비교를 위한 실행 (작은 배열에서만 실행)
small_array = large_array[:1000] # 처음 1000개 요소만 사용
target_small = random.choice(small_array)
start_time = time.time()
result_linear = small_array.index(target_small)
end_time = time.time()
print(f"\n작은 배열(1000개)에서:")
print(f"선형 검색 실행 시간: {end_time - start_time:.6f}초")
print(f"타겟 {target_small}의 인덱스: {result_linear}")
start_time = time.time()
result_binary = binary_search(small_array, target_small)
end_time = time.time()
print(f"이진 검색 실행 시간: {end_time - start_time:.6f}초")
print(f"타겟 {target_small}의 인덱스: {result_binary}")728x90