[Python] 알고리즘 개념20 - 이진 탐색(Binary Search)

 

🚀 1. 이진 탐색(Binary Search)이란?

**이진 탐색(Binary Search)**은 정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 알고리즘이에요.

 

💡 이진 탐색이 강력한 이유

• 선형 탐색(Linear Search, O(n))보다 훨씬 빠른 **O(log n)**의 성능을 가짐
• 큰 데이터에서 빠르게 검색 가능
• 정렬된 배열에서만 사용할 수 있음

 

📌 이진 탐색의 핵심 개념

1. 중간값(Pivot) 선택: 배열의 중앙값을 선택
2. 비교 후 반으로 나누기: 찾고자 하는 값이 중간값보다 크거나 작으면 탐색 범위를 절반으로 줄임
3. 반복 or 재귀: 위 과정을 반복하며 원하는 값을 찾음

➡ 정렬된 데이터에서 탐색할 때 매우 유용한 알고리즘이에요!

---

 

 

🚀 2. 이진 탐색과 선형 탐색 비교

 

📌 탐색 알고리즘 성능 비교

탐색 알고리즘 / 평균 시간 복잡도 / 최악 시간 복잡도 / 필요 조건

선형 탐색 (Linear Search)	O(n)	O(n)	정렬 필요 없음
이진 탐색 (Binary Search)	O(log n)	O(log n)	정렬된 배열

➡ 이진 탐색은 선형 탐색보다 훨씬 빠르지만, 반드시 정렬된 배열에서만 사용할 수 있어요!

---

 

 

🚀 3. 이진 탐색 개념 예제

 

예제 1: 도서관에서 책 찾기 📚

도서관에서 제목순으로 정렬된 책들 중에서 특정 책을 찾고 싶어요.

• 선형 탐색: 첫 번째 책부터 한 권씩 확인하면서 찾음 (비효율적)
• 이진 탐색: 가운데 책을 펼쳐보고 찾는 책보다 앞인지 뒤인지 판단하여 탐색 범위를 반으로 줄임 (효율적)

 

예제 2: 전화번호부에서 이름 찾기 ☎️

전화번호부는 알파벳 순으로 정렬되어 있어요.

• 특정 이름을 찾을 때 처음부터 하나씩 찾는 것보다, 중간을 열어보고 이름이 앞인지 뒤인지 확인하며 탐색 범위를 줄이는 방식이 더 효율적이에요.

➡ 이진 탐색은 이런 식으로 빠르게 데이터를 찾을 때 유용해요!

---

 

 

🚀 4. 이진 탐색 (반복문)

반복문을 활용한 이진 탐색은 탐색 범위를 직접 조정하며 값을 찾는 방식이에요.

 

💡 이진 탐색 (반복문)의 핵심 개념

1. 왼쪽(left)과 오른쪽(right) 포인터를 설정
2. 중간값(mid) 계산 후 비교
3. 조건에 따라 탐색 범위를 절반으로 줄이기

 

 

📌 Python 코드 구현 (반복문 방식)

def binary_search(arr, target):
    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  # 찾지 못한 경우

arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(arr, target))  # 출력: 3

➡ 반복문을 이용한 이진 탐색은 O(log n)의 시간 복잡도를 가져요!

---

 

 

🚀 5. 이진 탐색 (재귀 함수)

재귀 함수(Recursive Function)를 활용한 이진 탐색은 재귀적으로 탐색 범위를 좁혀가는 방식이에요.

 

 

📌 Python 코드 구현 (재귀 방식)

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, mid + 1, right)  # 오른쪽 탐색
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # 왼쪽 탐색

arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search_recursive(arr, target, 0, len(arr) - 1))  # 출력: 3

➡ 재귀를 활용한 이진 탐색도 O(log n)의 성능을 가지며, 코드가 직관적이에요

---

 

 

✅ 마무리 정리

• 이진 탐색(Binary Search): O(log n)의 빠른 탐색 알고리즘
• 반복문과 재귀를 활용한 구현 방식이 있음
• 정렬된 배열에서만 사용 가능
• 선형 탐색(Linear Search)보다 훨씬 빠른 성능
• 다양한 문제(파라메트릭 서치, 최적화 문제) 해결에 응용 가능