[알고리즘] 이진탐색 구현 재귀 방식 VS 반복 방식

 

Binary Search에서의 Recursive vs Iterative 전략 

 

 

1. 개요

알고리즘에서 동일한 문제를 해결하는 방법은 여러 가지가 존재한다.

 

대표적으로 Fibonacci 수열 구현 방식에서 사용되는 두 가지 전략이 있다.

• Recursive Strategy (재귀 방식)
• Iterative Strategy (반복문 방식)

이 두 가지 방식은 Binary Search(이진 탐색)에도 동일하게 적용할 수 있다.

 

 

 

 

2. Binary Search란?

Binary Search는 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘이다.

• 매 단계마다 탐색 범위를 절반으로 줄임
• 시간복잡도: O(log n)

 

 

 

3. Recursive 방식 (재귀)

 

 핵심 아이디어

• 문제를 더 작은 문제로 나눠서 해결
• 함수가 자기 자신을 호출

 

 

동작 흐름

1. 중간값(mid) 계산
2. target과 비교
3. 왼쪽 or 오른쪽 영역으로 재귀 호출

 

def binary_search_recursive(arr, target, left, right):
    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, left, mid - 1)
    else:
        return binary_search_recursive(arr, target, mid + 1, right)

 

 

특징

• 코드가 간결하고 직관적
• 함수 호출 스택 사용 → 메모리 사용 증가
• 깊은 재귀 시 Stack Overflow 위험

 

 

 

 

4. Iterative 방식 (반복문)

 

 

def binary_search_iterative(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    
    return -1

 

 

 

특징

• 메모리 효율적 (스택 사용 X)
• 일반적으로 더 빠름
• 코드가 재귀보다 약간 길지만 안정적

 

 

 

항목	Recursive	Iterative
구현 난이도	쉬움	보통
가독성	좋음	보통
메모리 사용	많음 (스택)	적음
성능	상대적으로 느림	빠름
안정성	낮음 (Stack overflow 가능)	높음

 

 

 

 

5. 결론

Binary Search는 Recursive와 Iterative 두 방식 모두 구현 가능하다.

• 학습/이해 목적 → Recursive 추천
• 실무/성능 → Iterative 추천

 

 

Binary Search는 문제를 절반씩 나누는 구조이기 때문에 재귀와 반복문 두 가지 방식 모두 자연스럽게 적용 가능하다.