이진 탐색이란 무엇인가?

이진 탐색이란 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘입니다. 업다운 게임과 같은 원리를 가지고 있습니다.

 

이진 탐색의 원리

이진 탐색은 아래와 같은 단계로 진행됩니다.

1. 배열의 중간 요소를 선택합니다.
2. 중간 요소와 찾고자 하는 값을 비교합니다.
3. 찾고자 하는 값이 중간 요소보다 작으면 왼쪽 부분 배열을, 크면 오른쪽 부분 배열을 대상으로 검색을 진행합니다.
4. 찾고자 하는 값을 찾거나 더 이상 검색할 수 없을 때까지 이 과정을 반복합니다.

이 방법을 사용하면 매 단계마다 검색 범위가 거의 절반이 줄어들어 O(log n)의 시간 복잡도를 가집니다.

 

---

 

 

 

파이썬에서 이진 탐색은 주로 두 가지 방법으로 구현됩니다.

반복문을 사용하는 방법과 재귀함수를 사용하는 방법입니다.

 

일단 반복문을 사용한 구현을 확인해보겠습니다.

def binary_search(array, target):
    start = 0
    end = len(array) - 1
    
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    
    return None

이 함수는 배열과 찾고자 하는 값을 입력받아 해당 값의 인덱스를 반환합니다. 찾지 못한 경우 None을 반환합니다.

 

 

다음은 재귀함수를 사용한 구현입니다.

def binary_search(array, target, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

재귀 함수를 사용한 방법도 동일한 로직을 따르지만, 함수가 자기 자신을 호출하는 방식으로 구현됩니다.

 

 

---

그러면 두 방법의 차이점을 알아보도록 하겠습니다.

 

구조적 차이

 

비재귀적 방법

1. while 루프를 사용하여 구현합니다.
2. 검색 범위를 나타내는 번수(start, end)를 직접 갱신합니다.
3. 루프가 종료될 때까지 반복합니다.

재귀적 방법

1. 함수가 자기 자신을 호출하는 방식으로 구현합니다.
2. 새로운 검색 범위를 매개변수로 전달하여 재귀 호출합니다.
3. 기저 조건(base case)에 도달하면 재귀를 종료합니다.

 

---

성능 차이

1. 일반적으로 비재귀적 방법이 재귀적 방법보다 약간 더 효율적입니다.
2. 재귀 호출은 함수 호출 오버헤드와 추가적인 스택 공간을 필요로 합니다.
   • 재귀 호출은 함수 호출 시 추가적인 연산이 필요합니다. 예를 들어:
     • 매개변수 복사
     • 지역변수 초기화
     • 반환 주소 저장 등이 있습니다.
   • cpu 시간을 소비합니다. 함수 호출과 반환 시 프로그램 실행 흐름이 변경되어 추가적인 처리 시간이 필요합니다.
   • 재귀 호출은 호출 스택(call stack)에 새로운 스택 프레임을 추가합니다.
     • 각 재귀호출마다 새로운 스택 프레임이 생성됩니다.
       1. 함수의 매개변수
       2. 지역변수
       3. 반환 주소
       4. 기타 함수 실행에 필요한 정보를 생성합니다.
     • 재귀 깊이가 깊어질수록 스택 사용량이 증가하고 이는 메모리 사용량 증가로 이어집니다.
       1. 이렇게 과도한 재귀는 스택 오버플로우를 일으킬 수 있고, 이는 프로그램의 실패 원인이 될 수 있습니다.

 

 

 

# 이 글의 내용 중 일부는 Perplexity AI의 도움을 받아 정보를 수집하고 정리하였으며, 추가적인 연구와 개인적인 견해를 더하였습니다.