탐색 알고리즘 (Search)

개념

데이터 집합에서 특정 값을 찾는 알고리즘

선형 탐색, 이진 탐색 등 다양한 방법 존재

---

탐색 알고리즘 비교

알고리즘	시간복잡도	공간복잡도	조건
선형 탐색	O(n)	O(1)	정렬 불필요
이진 탐색	O(log n)	O(1)	정렬 필수
해시 탐색	O(1)	O(n)	해시 테이블 필요

---

선형 탐색 (Linear Search)

개념

처음부터 끝까지 순차적으로 탐색하는 방법

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1
 
# 테스트
arr = [3, 1, 4, 1, 5, 9, 2]
print(linear_search(arr, 5))  # 4
print(linear_search(arr, 7))  # -1
 
# 시간복잡도: O(n)
# 공간복잡도: O(1)

특징

• 장점: 구현 간단, 정렬 불필요
• 단점: 데이터가 많으면 느림
• 활용: 작은 데이터, 정렬되지 않은 데이터

---

이진 탐색 (Binary Search)

개념

정렬된 배열에서 중간값과 비교하며 범위를 절반씩 줄여가는 탐색

[1, 3, 5, 7, 9, 11, 13, 15, 17]
         ↑
      target과 비교
   작으면 왼쪽, 크면 오른쪽 범위로 이동

---

1. 반복문 구현

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, 15]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 10))  # -1
 
# 시간복잡도: O(log n)
# 공간복잡도: O(1)

---

2. 재귀 구현

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, 15]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # 3
 
# 시간복잡도: O(log n)
# 공간복잡도: O(log n) - 재귀 호출 스택

---

3. Python bisect 모듈

import bisect
 
arr = [1, 3, 5, 7, 9, 11, 13, 15]
 
# bisect_left: target이 들어갈 가장 왼쪽 위치
index = bisect.bisect_left(arr, 7)
if index < len(arr) and arr[index] == 7:
    print(f"Found at index {index}")  # Found at index 3
 
# bisect_right: target이 들어갈 가장 오른쪽 위치
print(bisect.bisect_right(arr, 7))  # 4
 
# insort: 정렬을 유지하며 삽입
bisect.insort(arr, 6)
print(arr)  # [1, 3, 5, 6, 7, 9, 11, 13, 15]

---

이진 탐색 변형

1. Lower Bound (하한)

target 이상인 첫 번째 원소의 인덱스

def lower_bound(arr, target):
    left, right = 0, len(arr)
 
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
 
    return left
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(lower_bound(arr, 2))  # 1 (첫 번째 2의 위치)
 
# Python bisect 사용
import bisect
print(bisect.bisect_left(arr, 2))  # 1

---

2. Upper Bound (상한)

target보다 큰 첫 번째 원소의 인덱스

def upper_bound(arr, target):
    left, right = 0, len(arr)
 
    while left < right:
        mid = (left + right) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
 
    return left
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(upper_bound(arr, 2))  # 4 (2보다 큰 첫 위치)
 
# Python bisect 사용
import bisect
print(bisect.bisect_right(arr, 2))  # 4

---

3. 특정 값의 개수 세기

def count_occurrences(arr, target):
    left = bisect.bisect_left(arr, target)
    right = bisect.bisect_right(arr, target)
    return right - left
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2))  # 3

---

자주 나오는 문제 유형

1. 정렬된 배열에서 타겟 찾기

문제: 정렬된 배열에서 타겟의 시작과 끝 위치 찾기

def search_range(nums, target):
    def find_first():
        left, right = 0, len(nums) - 1
        result = -1
 
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                result = mid
                right = mid - 1  # 더 왼쪽 탐색
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
 
        return result
 
    def find_last():
        left, right = 0, len(nums) - 1
        result = -1
 
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                result = mid
                left = mid + 1  # 더 오른쪽 탐색
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
 
        return result
 
    return [find_first(), find_last()]
 
# 테스트
print(search_range([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
print(search_range([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]
 
# 시간복잡도: O(log n)

핵심: 이진 탐색을 두 번 수행 (첫 위치, 마지막 위치)

---

2. 회전된 정렬 배열 탐색

문제: 회전된 정렬 배열에서 타겟 찾기

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
 
    while left <= right:
        mid = (left + right) // 2
 
        if nums[mid] == target:
            return mid
 
        # 왼쪽이 정렬되어 있는 경우
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽이 정렬되어 있는 경우
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
 
    return -1
 
# 테스트
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1
 
# 시간복잡도: O(log n)

핵심: 정렬된 부분을 찾아 범위 결정

---

3. 제곱근 구하기

문제: 정수 x의 제곱근을 소수점 없이 구하기

def my_sqrt(x):
    if x < 2:
        return x
 
    left, right = 1, x // 2
 
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
 
        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1
 
    return right  # 소수점 버림
 
# 테스트
print(my_sqrt(4))   # 2
print(my_sqrt(8))   # 2
print(my_sqrt(16))  # 4
 
# 시간복잡도: O(log n)

핵심: 답의 범위에서 이진 탐색 (Parametric Search)

---

4. 나무 자르기

문제: 높이 H로 나무를 잘랐을 때 원하는 길이 이상 얻기

def cut_trees(trees, target):
    left, right = 0, max(trees)
    result = 0
 
    while left <= right:
        mid = (left + right) // 2
 
        # mid 높이로 잘랐을 때 얻는 나무 길이
        total = sum(max(0, tree - mid) for tree in trees)
 
        if total >= target:
            result = mid
            left = mid + 1  # 더 높게 잘라보기
        else:
            right = mid - 1
 
    return result
 
# 테스트
trees = [20, 15, 10, 17]
print(cut_trees(trees, 7))  # 15
 
# 시간복잡도: O(n log max(trees))

핵심: 답의 범위를 이진 탐색 (파라메트릭 서치)

---

5. 최소값 찾기 (회전된 정렬 배열)

문제: 회전된 정렬 배열에서 최소값 찾기

def find_min(nums):
    left, right = 0, len(nums) - 1
 
    while left < right:
        mid = (left + right) // 2
 
        # 중간값이 오른쪽 끝보다 크면 최소값은 오른쪽
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
 
    return nums[left]
 
# 테스트
print(find_min([3, 4, 5, 1, 2]))  # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
 
# 시간복잡도: O(log n)

핵심: 중간값과 오른쪽 끝 비교로 방향 결정

---

추천 연습 문제

기초

• 백준 1920번 - 수 찾기
• 백준 10816번 - 숫자 카드 2
• 백준 1654번 - 랜선 자르기

중급

• 백준 2805번 - 나무 자르기
• 백준 2110번 - 공유기 설치
• LeetCode 34 - Find First and Last Position
• LeetCode 33 - Search in Rotated Sorted Array

고급

• 백준 1300번 - K번째 수
• LeetCode 4 - Median of Two Sorted Arrays
• 백준 12015번 - 가장 긴 증가하는 부분 수열 2

---

핵심 요약

개념	설명
이진 탐색	정렬된 배열에서 O(log n) 탐색
Lower/Upper Bound	특정 값의 범위 찾기
Parametric Search	답의 범위에서 이진 탐색
bisect 모듈	Python 내장 이진 탐색 도구

---

이진 탐색 팁

1. 조건 확인

• 배열이 정렬되어 있는가?
• 정렬되지 않았다면 선형 탐색 또는 정렬 후 이진 탐색

2. 범위 설정

# 일반 이진 탐색
left, right = 0, len(arr) - 1
 
# Lower/Upper Bound
left, right = 0, len(arr)
 
# 파라메트릭 서치
left, right = min_value, max_value

3. 반복 조건

# 일반
while left <= right:
 
# Lower/Upper Bound
while left < right:

4. mid 계산 시 주의

# 오버플로우 방지 (큰 수일 때)
mid = left + (right - left) // 2
 
# 일반적인 경우
mid = (left + right) // 2

---

파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제로 바꿔 이진 탐색

템플릿

def parametric_search(start, end):
    result = 0
 
    while start <= end:
        mid = (start + end) // 2
 
        if is_possible(mid):  # mid 값으로 조건 만족?
            result = mid
            start = mid + 1   # 더 큰 값 시도
        else:
            end = mid - 1     # 더 작은 값 시도
 
    return result

활용

• 나무 자르기
• 공유기 설치
• 징검다리
• 예산 배정