이진 탐색(Binary Search) 완전 정복: 원리, 구현, 실전 문제까지

이진 탐색(Binary Search) 완전 정복: 원리, 구현, 실전 문제까지

**이진 탐색(Binary Search)**은 알고리즘 학습에서 가장 기본이자 강력한 기법입니다.
데이터가 정렬된 상태라는 전제 하에, 탐색 범위를 절반씩 줄여가며 원하는 값을 찾는 효율적인 방법입니다.

이번 글에서는 이진 탐색의 원리부터 재귀/반복 구현 방식, 탐색 실패 시 인덱스 처리, 실전 문제 적용법까지 모두 정리합니다.

---

✅ 이진 탐색(Binary Search)이란?

이진 탐색은 정렬된 배열에서 원하는 값을 찾기 위해, 중앙값과 비교하여 탐색 범위를 반으로 줄여나가는 방식입니다.

📌 동작 과정 요약

1. 중간 인덱스를 찾는다.
2. 중간값과 타겟 값을 비교한다.
   • 중간값 == 타겟 → 정답
   • 중간값 < 타겟 → 오른쪽 절반 탐색
   • 중간값 > 타겟 → 왼쪽 절반 탐색
3. 탐색 범위가 사라질 때까지 반복

⏱ 시간 복잡도

• O(log n) — 탐색 범위가 매 단계마다 반으로 줄어듦

---

🧪 이진 탐색 – 반복문 방식 (Iterative)

반응형

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]
print(binary_search(arr, 7))   # 출력: 3
print(binary_search(arr, 4))   # 출력: -1

---

🧠 이진 탐색 – 재귀 함수 방식 (Recursive)

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)

print(binary_search_recursive(arr, 11, 0, len(arr) - 1))  # 출력: 5

---

⚠️ 실전에서 주의할 점

✅ 탐색 실패 시 인덱스를 어떻게 활용할까?

• 보통 -1을 반환하지만, **삽입 가능한 위치(index)**가 필요한 경우도 있음
  → 이진 탐색 응용: bisect 모듈 사용

import bisect

arr = [1, 3, 5, 7]
print(bisect.bisect_left(arr, 4))  # 출력: 2 (4를 넣을 위치)
print(bisect.bisect_right(arr, 4)) # 출력: 2

---

🚀 실전 문제 예제: 숫자 존재 여부 판별

❓ 문제

정렬된 수열에서 특정 수 x가 존재하는지 이진 탐색으로 판별하라.

✅ 코드

def exists(arr, x):
    return binary_search(arr, x) != -1

print(exists([2, 4, 6, 8, 10], 8))  # True
print(exists([2, 4, 6, 8, 10], 7))  # False

---

🔄 응용 패턴: Lower Bound / Upper Bound

• Lower Bound: target 이상이 처음 나오는 위치
• Upper Bound: target 초과가 처음 나오는 위치

import bisect

arr = [1, 2, 4, 4, 4, 5, 7]
print(bisect.bisect_left(arr, 4))  # 출력: 2
print(bisect.bisect_right(arr, 4)) # 출력: 5

→ [4, 4, 4] 구간의 개수는 5 - 2 = 3

---

🧩 이진 탐색이 쓰이는 실전 문제 유형

문제 유형 설명

값 찾기	정렬된 리스트에서 특정 값 탐색
개수 세기	값의 등장 횟수 (lower/upper bound 사용)
파라메트릭 서치	조건을 만족하는 최소/최대값 찾기
최적화 문제	조건을 만족하는 가장 작은/큰 수 구하기
결정 문제	"조건 만족 여부" → 이진 탐색으로 판단

---

📌 결론 및 요약

• 이진 탐색은 정렬된 배열에서 **O(log n)**의 속도로 값을 찾을 수 있는 강력한 알고리즘입니다.
• 반복, 재귀, bisect 등 다양한 방식으로 구현 가능하며, 응용 폭도 넓습니다.
• 코딩테스트에서는 탐색 + 조건 검증 패턴으로 자주 출제됩니다.

👉 다음 글에서는 정렬 알고리즘의 종류와 시간복잡도 비교, 그리고 실제 코드 구현을 소개하겠습니다!

---

📚 참고자료 및 출처

• 『이것이 취업을 위한 코딩 테스트다 with 파이썬』
• Python bisect 모듈 공식 문서: https://docs.python.org/3/library/bisect.html
• GeeksforGeeks – Binary Search

---

 

이진탐색, binary search, bisect, 파이썬 알고리즘, 탐색 알고리즘, lower bound, upper bound, 코딩테스트, 시간복잡도, SEO 최적화 10개