[CS 기초 #13] 탐색 알고리즘: 선형 탐색부터 이진 탐색까지 완벽 가이드

찾아라! 선형 탐색부터 이진 탐색, DFS, BFS까지 모든 탐색 방법을 마스터합니다.

🎯 이 글을 읽고 나면

• 선형 탐색과 이진 탐색의 차이를 명확히 안다
• 이진 탐색의 조건과 구현 방법을 이해합니다
• DFS와 BFS의 차이와 활용을 설명할 수 있습니다
• 완전 탐색과 백트래킹을 구분할 수 있습니다
• 각 탐색 방법의 시간 복잡도를 비교할 수 있습니다

📚 사전 지식

• 이진 탐색 기초: 정렬된 배열 개념
• 그래프: 이전 글: 그래프 - DFS/BFS
• 시간 복잡도: O(n) vs O(log n) 이해

💡 핵심 개념 미리보기

탐색(Search)은 원하는 데이터를 찾는 과정입니다. 선형 탐색(O(n))은 단순하지만 느리고, 이진 탐색(O(log n))은 정렬된 데이터에서 매우 빠릅니다. 그래프에서는 DFS(깊이 우선)와 BFS(너비 우선)를 사용하며, 모든 경우를 확인하는 완전 탐색도 중요합니다!

---

🔍 들어가며: 탐색의 중요성

구글은 어떻게 수십억 개의 웹페이지에서 원하는 정보를 순식간에 찾을까요? 데이터베이스는 어떻게 수백만 개의 레코드에서 특정 데이터를 밀리초 안에 찾을까요?

오늘은 탐색 알고리즘의 모든 것을 다룹니다. 단순한 선형 탐색부터 효율적인 이진 탐색, 그리고 특수한 상황에서 사용하는 고급 탐색 기법까지 완벽하게 알아보겠습니다!

📊 탐색 알고리즘 개요

graph TB
    subgraph "탐색 알고리즘 분류"
        Linear[선형 탐색<br/>O(n)]
        Divide[분할 탐색<br/>O(log n)]
        Hash[해시 탐색<br/>O(1)]
        Tree[트리 탐색<br/>O(log n)~O(n)]
    end
    
    Linear --> LS[선형 탐색]
    Linear --> SS[센티널 탐색]
    
    Divide --> BS[이진 탐색]
    Divide --> IS[보간 탐색]
    Divide --> ES[지수 탐색]
    Divide --> JS[점프 탐색]
    
    Hash --> HT[해시 테이블]
    Hash --> BF[블룸 필터]
    
    Tree --> BST[이진 탐색 트리]
    Tree --> BTree[B-트리]

탐색 알고리즘 성능 비교

def search_algorithm_comparison():
    """탐색 알고리즘 성능 비교"""
    
    algorithms = {
        "선형 탐색": {
            "최선": "O(1)",
            "평균": "O(n)",
            "최악": "O(n)",
            "전제조건": "없음",
            "공간": "O(1)"
        },
        "이진 탐색": {
            "최선": "O(1)",
            "평균": "O(log n)",
            "최악": "O(log n)",
            "전제조건": "정렬된 배열",
            "공간": "O(1)"
        },
        "보간 탐색": {
            "최선": "O(1)",
            "평균": "O(log log n)",
            "최악": "O(n)",
            "전제조건": "정렬 + 균등 분포",
            "공간": "O(1)"
        },
        "점프 탐색": {
            "최선": "O(1)",
            "평균": "O(√n)",
            "최악": "O(√n)",
            "전제조건": "정렬된 배열",
            "공간": "O(1)"
        },
        "지수 탐색": {
            "최선": "O(1)",
            "평균": "O(log n)",
            "최악": "O(log n)",
            "전제조건": "정렬된 배열",
            "공간": "O(1)"
        },
        "해시 탐색": {
            "최선": "O(1)",
            "평균": "O(1)",
            "최악": "O(n)",
            "전제조건": "해시 테이블",
            "공간": "O(n)"
        }
    }
    
    print("탐색 알고리즘 성능 비교:")
    print("-" * 90)
    print(f"{'알고리즘':<12} {'최선':<10} {'평균':<15} {'최악':<10} {'전제조건':<20} {'공간':<10}")
    print("-" * 90)
    
    for name, perf in algorithms.items():
        print(f"{name:<12} {perf['최선']:<10} {perf['평균']:<15} {perf['최악']:<10} "
              f"{perf['전제조건']:<20} {perf['공간']:<10}")

search_algorithm_comparison()

🔍 선형 탐색 (Linear Search)

기본 선형 탐색

def linear_search(arr, target):
    """선형 탐색 - O(n)
    배열을 처음부터 끝까지 순차적으로 탐색
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

def linear_search_with_stats(arr, target):
    """통계 정보를 포함한 선형 탐색"""
    comparisons = 0
    
    for i in range(len(arr)):
        comparisons += 1
        if arr[i] == target:
            print(f"찾음! 위치: {i}, 비교 횟수: {comparisons}")
            return i
    
    print(f"찾지 못함. 비교 횟수: {comparisons}")
    return -1

# 테스트
arr = [64, 34, 25, 12, 22, 11, 90]
print(f"배열: {arr}")
linear_search_with_stats(arr, 22)
linear_search_with_stats(arr, 100)

센티널 선형 탐색

def sentinel_linear_search(arr, target):
    """센티널 선형 탐색 - 최적화된 선형 탐색
    마지막에 센티널을 추가하여 경계 검사 제거
    """
    n = len(arr)
    last = arr[n - 1]
    
    # 센티널 설정
    arr[n - 1] = target
    
    i = 0
    while arr[i] != target:
        i += 1
    
    # 원래 값 복원
    arr[n - 1] = last
    
    # 찾은 위치 확인
    if i < n - 1 or last == target:
        return i
    
    return -1

# 성능 비교
import time

def compare_linear_searches():
    """일반 선형 탐색 vs 센티널 선형 탐색"""
    import random
    
    arr = [random.randint(1, 1000) for _ in range(10000)]
    target = -1  # 없는 값 (최악의 경우)
    
    # 일반 선형 탐색
    start = time.perf_counter()
    for _ in range(100):
        linear_search(arr.copy(), target)
    normal_time = time.perf_counter() - start
    
    # 센티널 선형 탐색
    start = time.perf_counter()
    for _ in range(100):
        sentinel_linear_search(arr.copy(), target)
    sentinel_time = time.perf_counter() - start
    
    print(f"일반 선형 탐색: {normal_time:.4f}초")
    print(f"센티널 선형 탐색: {sentinel_time:.4f}초")
    print(f"성능 향상: {(normal_time - sentinel_time) / normal_time * 100:.1f}%")

compare_linear_searches()

정렬된 배열에서의 선형 탐색

def linear_search_sorted(arr, target):
    """정렬된 배열에서의 선형 탐색
    target보다 큰 값을 만나면 조기 종료
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
        elif arr[i] > target:
            return -1  # 조기 종료
    return -1

def linear_search_multiple(arr, target):
    """모든 일치하는 원소 찾기"""
    indices = []
    for i in range(len(arr)):
        if arr[i] == target:
            indices.append(i)
    return indices

# 테스트
sorted_arr = [1, 3, 3, 5, 7, 7, 7, 9, 11]
print(f"정렬된 배열: {sorted_arr}")
print(f"7의 모든 위치: {linear_search_multiple(sorted_arr, 7)}")

🎯 이진 탐색 (Binary Search)

기본 이진 탐색

def binary_search_iterative(arr, target):
    """반복적 이진 탐색 - O(log n)"""
    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=0, right=None):
    """재귀적 이진 탐색 - O(log n)"""
    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 binary_search_visualization(arr, target):
    """이진 탐색 시각화"""
    left, right = 0, len(arr) - 1
    step = 0
    
    print(f"배열: {arr}")
    print(f"찾는 값: {target}\n")
    
    while left <= right:
        mid = (left + right) // 2
        step += 1
        
        print(f"단계 {step}:")
        print(f"  범위: [{left}, {right}]")
        print(f"  중간 인덱스: {mid}, 값: {arr[mid]}")
        
        # 탐색 범위 시각화
        visual = [' '] * len(arr)
        for i in range(left, right + 1):
            visual[i] = '█'
        visual[mid] = '▲'
        
        print(f"  ", end="")
        for i, v in enumerate(visual):
            print(f"{v:2}", end="")
        print()
        print(f"  ", end="")
        for i in range(len(arr)):
            print(f"{arr[i]:2}", end="")
        print("\n")
        
        if arr[mid] == target:
            print(f"✓ 찾음! 인덱스: {mid}")
            return mid
        elif arr[mid] < target:
            print(f"  → {arr[mid]} < {target}, 오른쪽 탐색")
            left = mid + 1
        else:
            print(f"  → {arr[mid]} > {target}, 왼쪽 탐색")
            right = mid - 1
    
    print("✗ 찾지 못함")
    return -1

# 시각화 테스트
sorted_arr = [2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78]
binary_search_visualization(sorted_arr, 23)

이진 탐색 변형

def binary_search_first_occurrence(arr, target):
    """첫 번째 출현 위치 찾기"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 왼쪽 계속 탐색
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

def binary_search_last_occurrence(arr, target):
    """마지막 출현 위치 찾기"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            left = mid + 1  # 오른쪽 계속 탐색
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

def count_occurrences(arr, target):
    """이진 탐색으로 원소 개수 세기"""
    first = binary_search_first_occurrence(arr, target)
    
    if first == -1:
        return 0
    
    last = binary_search_last_occurrence(arr, target)
    return last - first + 1

def binary_search_closest(arr, target):
    """가장 가까운 값 찾기"""
    left, right = 0, len(arr) - 1
    
    if target <= arr[0]:
        return 0
    if target >= arr[-1]:
        return 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
    
    # left와 right 중 더 가까운 것 선택
    if left < len(arr) and (right < 0 or 
        abs(arr[left] - target) < abs(arr[right] - target)):
        return left
    return right

# 테스트
arr_with_duplicates = [1, 2, 2, 2, 3, 4, 4, 5, 6, 7]
print(f"배열: {arr_with_duplicates}")
print(f"2의 첫 번째 위치: {binary_search_first_occurrence(arr_with_duplicates, 2)}")
print(f"2의 마지막 위치: {binary_search_last_occurrence(arr_with_duplicates, 2)}")
print(f"2의 개수: {count_occurrences(arr_with_duplicates, 2)}")
print(f"3.5에 가장 가까운 값의 인덱스: {binary_search_closest(arr_with_duplicates, 3.5)}")

이진 탐색 응용

def search_in_rotated_array(arr, target):
    """회전된 정렬 배열에서 탐색
    예: [4, 5, 6, 7, 0, 1, 2]
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        
        # 왼쪽 부분이 정렬되어 있는 경우
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽 부분이 정렬되어 있는 경우
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

def search_in_2d_matrix(matrix, target):
    """2D 행렬에서 이진 탐색
    각 행이 정렬되고, 각 행의 첫 원소가 이전 행의 마지막 원소보다 큰 경우
    """
    if not matrix or not matrix[0]:
        return False
    
    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1
    
    while left <= right:
        mid = (left + right) // 2
        mid_value = matrix[mid // cols][mid % cols]
        
        if mid_value == target:
            return True
        elif mid_value < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return False

# 테스트
rotated = [4, 5, 6, 7, 0, 1, 2]
print(f"회전된 배열: {rotated}")
print(f"0의 위치: {search_in_rotated_array(rotated, 0)}")

matrix = [
    [1,  3,  5,  7],
    [10, 11, 16, 20],
    [23, 30, 34, 60]
]
print(f"\n2D 행렬에서 3 찾기: {search_in_2d_matrix(matrix, 3)}")
print(f"2D 행렬에서 13 찾기: {search_in_2d_matrix(matrix, 13)}")

🚀 고급 탐색 알고리즘

보간 탐색 (Interpolation Search)

def interpolation_search(arr, target):
    """보간 탐색 - 평균 O(log log n)
    균등 분포 데이터에서 효율적
    """
    left, right = 0, len(arr) - 1
    
    while left <= right and arr[left] <= target <= arr[right]:
        # 균등 분포 가정하에 위치 추정
        if arr[left] == arr[right]:
            if arr[left] == target:
                return left
            return -1
        
        # 보간 공식
        pos = left + ((target - arr[left]) * (right - left) // 
                     (arr[right] - arr[left]))
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

def interpolation_search_visualization(arr, target):
    """보간 탐색 시각화"""
    left, right = 0, len(arr) - 1
    step = 0
    
    print(f"배열: {arr}")
    print(f"찾는 값: {target}\n")
    
    while left <= right and arr[left] <= target <= arr[right]:
        step += 1
        
        if arr[left] == arr[right]:
            if arr[left] == target:
                print(f"✓ 찾음! 인덱스: {left}")
                return left
            print("✗ 찾지 못함")
            return -1
        
        # 보간 위치 계산
        pos = left + ((target - arr[left]) * (right - left) // 
                     (arr[right] - arr[left]))
        
        print(f"단계 {step}:")
        print(f"  범위: [{left}, {right}] = [{arr[left]}, {arr[right]}]")
        print(f"  보간 위치: {pos}, 값: {arr[pos]}")
        
        if arr[pos] == target:
            print(f"✓ 찾음! 인덱스: {pos}")
            return pos
        elif arr[pos] < target:
            print(f"  → {arr[pos]} < {target}, 오른쪽 탐색")
            left = pos + 1
        else:
            print(f"  → {arr[pos]} > {target}, 왼쪽 탐색")
            right = pos - 1
        print()
    
    print("✗ 찾지 못함")
    return -1

# 균등 분포 데이터에서 테스트
uniform_arr = list(range(0, 100, 2))  # [0, 2, 4, ..., 98]
print("균등 분포 데이터:")
interpolation_search_visualization(uniform_arr, 44)

점프 탐색 (Jump Search)

import math

def jump_search(arr, target):
    """점프 탐색 - O(√n)
    정렬된 배열에서 블록 단위로 점프하며 탐색
    """
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    
    # 블록 점프
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    
    # 선형 탐색
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    
    if arr[prev] == target:
        return prev
    
    return -1

def jump_search_optimized(arr, target):
    """최적화된 점프 탐색
    마지막 블록에서 이진 탐색 사용
    """
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    
    # 블록 점프
    while prev < n and arr[min(prev + step, n) - 1] < target:
        prev += step
    
    # 마지막 블록에서 이진 탐색
    left = prev
    right = min(prev + step, n) - 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 jump_search_visualization(arr, target):
    """점프 탐색 시각화"""
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    jump_count = 0
    
    print(f"배열 크기: {n}, 점프 크기: {step}")
    print(f"찾는 값: {target}\n")
    
    # 블록 점프
    while arr[min(step, n) - 1] < target:
        jump_count += 1
        print(f"점프 {jump_count}: 인덱스 {prev} → {step}")
        print(f"  값: {arr[prev]} → {arr[min(step, n) - 1]}")
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            print("✗ 범위 초과")
            return -1
    
    print(f"\n블록 찾음: [{prev}, {min(step, n) - 1}]")
    print("선형 탐색 시작...")
    
    # 선형 탐색
    comparisons = 0
    while arr[prev] < target:
        comparisons += 1
        prev += 1
        if prev == min(step, n):
            print(f"✗ 찾지 못함 (비교 횟수: {comparisons})")
            return -1
    
    if arr[prev] == target:
        print(f"✓ 찾음! 인덱스: {prev} (비교 횟수: {comparisons})")
        return prev
    
    print(f"✗ 찾지 못함 (비교 횟수: {comparisons})")
    return -1

# 테스트
arr = list(range(0, 100, 3))
print(f"배열: {arr[:10]}... (총 {len(arr)}개)")
jump_search_visualization(arr, 42)

지수 탐색 (Exponential Search)

def exponential_search(arr, target):
    """지수 탐색 - O(log n)
    무한 또는 크기를 모르는 배열에서 유용
    """
    n = len(arr)
    
    # 경계 조건
    if arr[0] == target:
        return 0
    
    # 범위를 지수적으로 증가
    i = 1
    while i < n and arr[i] <= target:
        i *= 2
    
    # 이진 탐색
    left = i // 2
    right = min(i, n - 1)
    
    return binary_search_in_range(arr, target, left, right)

def binary_search_in_range(arr, target, left, right):
    """범위 내 이진 탐색"""
    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 exponential_search_unbounded(arr, target):
    """무한 배열에서의 지수 탐색 시뮬레이션"""
    # 배열 크기를 모른다고 가정
    i = 1
    
    # 범위 찾기
    while True:
        try:
            if arr[i] >= target:
                break
            i *= 2
        except IndexError:
            # 배열 끝에 도달
            break
    
    # 이진 탐색
    left = i // 2
    right = min(i, len(arr) - 1)
    
    while left <= right:
        mid = (left + right) // 2
        
        try:
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        except IndexError:
            right = mid - 1
    
    return -1

# 테스트
arr = [1, 2, 3, 4, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
print(f"배열: {arr}")
print(f"55의 위치: {exponential_search(arr, 55)}")
print(f"100의 위치: {exponential_search(arr, 100)}")

🌲 트리 기반 탐색

이진 탐색 트리 (BST)

class BSTNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinarySearchTree:
    """이진 탐색 트리"""
    
    def __init__(self):
        self.root = None
        self.comparisons = 0
    
    def insert(self, value):
        """삽입 - 평균 O(log n), 최악 O(n)"""
        if not self.root:
            self.root = BSTNode(value)
        else:
            self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = BSTNode(value)
            else:
                self._insert_recursive(node.left, value)
        else:
            if node.right is None:
                node.right = BSTNode(value)
            else:
                self._insert_recursive(node.right, value)
    
    def search(self, value):
        """탐색 - 평균 O(log n), 최악 O(n)"""
        self.comparisons = 0
        result = self._search_recursive(self.root, value)
        print(f"비교 횟수: {self.comparisons}")
        return result
    
    def _search_recursive(self, node, value):
        if node is None:
            return False
        
        self.comparisons += 1
        
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)
    
    def search_iterative(self, value):
        """반복적 탐색"""
        current = self.root
        comparisons = 0
        
        while current:
            comparisons += 1
            if current.value == value:
                print(f"비교 횟수: {comparisons}")
                return True
            elif value < current.value:
                current = current.left
            else:
                current = current.right
        
        print(f"비교 횟수: {comparisons}")
        return False
    
    def find_min(self):
        """최솟값 찾기"""
        if not self.root:
            return None
        
        current = self.root
        while current.left:
            current = current.left
        return current.value
    
    def find_max(self):
        """최댓값 찾기"""
        if not self.root:
            return None
        
        current = self.root
        while current.right:
            current = current.right
        return current.value
    
    def inorder_traversal(self):
        """중위 순회 - 정렬된 순서로 출력"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.value)
            self._inorder_recursive(node.right, result)

# BST 테스트
bst = BinarySearchTree()
values = [50, 30, 70, 20, 40, 60, 80]
for val in values:
    bst.insert(val)

print(f"BST 중위 순회: {bst.inorder_traversal()}")
print(f"최솟값: {bst.find_min()}")
print(f"최댓값: {bst.find_max()}")
print(f"\n40 탐색: {bst.search(40)}")
print(f"45 탐색: {bst.search(45)}")

균형 이진 탐색 트리

class AVLNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    """AVL 트리 - 자가 균형 이진 탐색 트리"""
    
    def __init__(self):
        self.root = None
    
    def height(self, node):
        if not node:
            return 0
        return node.height
    
    def balance_factor(self, node):
        if not node:
            return 0
        return self.height(node.left) - self.height(node.right)
    
    def update_height(self, node):
        if node:
            node.height = 1 + max(self.height(node.left), 
                                 self.height(node.right))
    
    def rotate_right(self, y):
        """우회전"""
        x = y.left
        T2 = x.right
        
        x.right = y
        y.left = T2
        
        self.update_height(y)
        self.update_height(x)
        
        return x
    
    def rotate_left(self, x):
        """좌회전"""
        y = x.right
        T2 = y.left
        
        y.left = x
        x.right = T2
        
        self.update_height(x)
        self.update_height(y)
        
        return y
    
    def insert(self, value):
        """삽입 - O(log n) 보장"""
        self.root = self._insert_recursive(self.root, value)
    
    def _insert_recursive(self, node, value):
        # 일반 BST 삽입
        if not node:
            return AVLNode(value)
        
        if value < node.value:
            node.left = self._insert_recursive(node.left, value)
        else:
            node.right = self._insert_recursive(node.right, value)
        
        # 높이 업데이트
        self.update_height(node)
        
        # 균형 확인 및 회전
        balance = self.balance_factor(node)
        
        # Left-Left
        if balance > 1 and value < node.left.value:
            return self.rotate_right(node)
        
        # Right-Right
        if balance < -1 and value > node.right.value:
            return self.rotate_left(node)
        
        # Left-Right
        if balance > 1 and value > node.left.value:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        
        # Right-Left
        if balance < -1 and value < node.right.value:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        
        return node
    
    def search(self, value):
        """탐색 - O(log n) 보장"""
        return self._search_recursive(self.root, value)
    
    def _search_recursive(self, node, value):
        if not node:
            return False
        
        if node.value == value:
            return True
        elif value < node.value:
            return self._search_recursive(node.left, value)
        else:
            return self._search_recursive(node.right, value)

# AVL 트리 테스트
avl = AVLTree()
values = [10, 20, 30, 40, 50, 25]
for val in values:
    avl.insert(val)
    print(f"삽입 {val}, 루트: {avl.root.value if avl.root else None}")

print(f"\n25 탐색: {avl.search(25)}")
print(f"35 탐색: {avl.search(35)}")

💾 해시 기반 탐색

class HashTable:
    """해시 테이블을 이용한 탐색"""
    
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
        self.count = 0
    
    def _hash(self, key):
        """해시 함수"""
        return hash(key) % self.size
    
    def insert(self, key, value):
        """삽입 - 평균 O(1)"""
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
        self.count += 1
        
        # 로드 팩터 확인
        if self.count > self.size * 0.75:
            self._resize()
    
    def search(self, key):
        """탐색 - 평균 O(1)"""
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return None
    
    def _resize(self):
        """리사이징"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)
    
    def get_stats(self):
        """통계 정보"""
        non_empty = sum(1 for bucket in self.table if bucket)
        max_chain = max(len(bucket) for bucket in self.table)
        avg_chain = self.count / non_empty if non_empty > 0 else 0
        
        return {
            "size": self.size,
            "count": self.count,
            "load_factor": self.count / self.size,
            "non_empty_buckets": non_empty,
            "max_chain_length": max_chain,
            "avg_chain_length": avg_chain
        }

# 해시 테이블 테스트
ht = HashTable(5)
items = [("apple", 100), ("banana", 200), ("orange", 300), 
         ("grape", 400), ("melon", 500), ("peach", 600)]

for key, value in items:
    ht.insert(key, value)

print("해시 테이블 통계:")
for key, value in ht.get_stats().items():
    print(f"  {key}: {value}")

print(f"\napple 탐색: {ht.search('apple')}")
print(f"mango 탐색: {ht.search('mango')}")

🎯 실전 응용

1. 범위 탐색

def range_search(arr, low, high):
    """정렬된 배열에서 범위 내 모든 원소 찾기"""
    # 시작 위치 찾기
    start = binary_search_first_greater_equal(arr, low)
    if start == -1:
        return []
    
    # 끝 위치 찾기
    end = binary_search_last_less_equal(arr, high)
    if end == -1:
        return []
    
    return arr[start:end+1]

def binary_search_first_greater_equal(arr, target):
    """target 이상인 첫 번째 원소"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] >= target:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    
    return result

def binary_search_last_less_equal(arr, target):
    """target 이하인 마지막 원소"""
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] <= target:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return result

# 테스트
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(f"배열: {arr}")
print(f"5~13 범위: {range_search(arr, 5, 13)}")
print(f"6~14 범위: {range_search(arr, 6, 14)}")

2. 피크 원소 찾기

def find_peak_element(arr):
    """피크 원소 찾기 - O(log n)
    피크: 이웃보다 큰 원소
    """
    left, right = 0, len(arr) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] > arr[mid + 1]:
            # 왼쪽에 피크 존재
            right = mid
        else:
            # 오른쪽에 피크 존재
            left = mid + 1
    
    return left

def find_all_peaks(arr):
    """모든 피크 원소 찾기"""
    peaks = []
    n = len(arr)
    
    for i in range(n):
        is_peak = True
        
        # 왼쪽 확인
        if i > 0 and arr[i] <= arr[i-1]:
            is_peak = False
        
        # 오른쪽 확인
        if i < n-1 and arr[i] <= arr[i+1]:
            is_peak = False
        
        if is_peak:
            peaks.append(i)
    
    return peaks

# 테스트
arr = [1, 3, 20, 4, 1, 0, 8, 6]
print(f"배열: {arr}")
print(f"피크 원소 인덱스: {find_peak_element(arr)}")
print(f"모든 피크: {find_all_peaks(arr)}")

3. 중복 원소 탐색

def find_duplicate_binary_search(arr):
    """정렬된 배열에서 중복 원소 찾기"""
    duplicates = []
    i = 0
    
    while i < len(arr) - 1:
        if arr[i] == arr[i + 1]:
            value = arr[i]
            duplicates.append(value)
            
            # 같은 값 건너뛰기
            while i < len(arr) and arr[i] == value:
                i += 1
        else:
            i += 1
    
    return duplicates

def find_duplicate_floyd(nums):
    """Floyd's Cycle Detection으로 중복 찾기
    1~n 범위의 n+1개 숫자 중 하나의 중복
    """
    # 토끼와 거북이
    slow = fast = nums[0]
    
    # 사이클 찾기
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    
    # 사이클 시작점 찾기
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    
    return slow

# 테스트
sorted_arr = [1, 2, 2, 3, 4, 4, 4, 5, 6, 6]
print(f"정렬된 배열: {sorted_arr}")
print(f"중복 원소: {find_duplicate_binary_search(sorted_arr)}")

nums = [1, 3, 4, 2, 2]
print(f"\n배열: {nums}")
print(f"중복 원소 (Floyd): {find_duplicate_floyd(nums)}")

📊 탐색 알고리즘 성능 비교

import time
import random

def performance_comparison():
    """탐색 알고리즘 성능 비교"""
    sizes = [1000, 10000, 100000]
    
    print("탐색 알고리즘 성능 비교 (μs)")
    print("-" * 70)
    print(f"{'크기':<10} {'선형':<12} {'이진':<12} {'보간':<12} {'점프':<12}")
    print("-" * 70)
    
    for size in sizes:
        # 정렬된 데이터 생성
        arr = sorted([random.randint(1, size * 10) for _ in range(size)])
        target = arr[size // 2]  # 중간 원소
        
        results = {}
        
        # 선형 탐색
        start = time.perf_counter()
        linear_search(arr, target)
        results['linear'] = (time.perf_counter() - start) * 1000000
        
        # 이진 탐색
        start = time.perf_counter()
        binary_search_iterative(arr, target)
        results['binary'] = (time.perf_counter() - start) * 1000000
        
        # 보간 탐색
        start = time.perf_counter()
        interpolation_search(arr, target)
        results['interpolation'] = (time.perf_counter() - start) * 1000000
        
        # 점프 탐색
        start = time.perf_counter()
        jump_search(arr, target)
        results['jump'] = (time.perf_counter() - start) * 1000000
        
        print(f"{size:<10} {results['linear']:<12.2f} {results['binary']:<12.2f} "
              f"{results['interpolation']:<12.2f} {results['jump']:<12.2f}")

performance_comparison()

🎯 핵심 정리

꼭 기억해야 할 5가지

1. 선형 탐색: 정렬 불필요, O(n), 작은 데이터에 적합
2. 이진 탐색: 정렬 필요, O(log n), 가장 범용적
3. 보간 탐색: 균등 분포에서 O(log log n)
4. 해시 탐색: 평균 O(1), 메모리 추가 필요
5. 트리 탐색: 동적 데이터, 범위 탐색에 유용

알고리즘 선택 가이드

• 정렬되지 않은 데이터: 선형 탐색 또는 해시
• 정렬된 데이터: 이진 탐색
• 균등 분포 데이터: 보간 탐색
• 동적 데이터: BST 또는 AVL 트리
• 빈번한 탐색: 해시 테이블

📚 추가 학습 자료

추천 문제

• LeetCode: Binary Search, Search in Rotated Sorted Array, Find Peak Element
• 프로그래머스: 입국심사, 징검다리, 순위 검색
• 백준: 1920(수 찾기), 2805(나무 자르기), 1654(랜선 자르기)

🚀 다음 시간 예고

다음 포스트에서는 동적 계획법(Dynamic Programming)을 다룹니다. 복잡한 문제를 작은 부분 문제로 나누어 해결하는 강력한 기법을 알아보겠습니다!

---

📌 시리즈 네비게이션

순서	제목	링크
12	정렬 알고리즘: 버블 정렬부터 퀵 정렬까지	← 이전 글
13	탐색 알고리즘: 선형 탐색부터 이진 탐색까지 ✅	현재 글
14	동적 계획법: 복잡한 문제를 단순하게	다음 글 →

📋 전체 시리즈 목차 보기

기초 이론편

1. CS 입문 ✅
2. 컴퓨터 구조 ✅
3. 이진수와 논리 게이트 ✅
4. 운영체제 기초 ✅
5. 네트워크 기초 ✅

자료구조편

1. 배열과 연결 리스트 ✅
2. 스택과 큐 ✅
3. 트리 구조 ✅
4. 그래프 ✅
5. 해시 테이블 ✅

알고리즘편

1. 복잡도 분석 ✅
2. 정렬 알고리즘 ✅
3. 탐색 알고리즘 ✅
4. 동적 계획법
5. 그리디와 분할정복

실무 응용편

1. 데이터베이스 이론
2. 소프트웨어 공학
3. 보안 기초
4. 분산 시스템
5. CS 종합과 면접 준비