이진탐색

✅ 이진탐색(Binary Search) 개념

정렬된 배열(혹은 리스트)에서 탐색 범위를 절반씩 줄여가며 원하는 값을 빠르게 찾는 알고리즘

• 시간복잡도: O(log N)
• 전제 조건: 배열이나 탐색 대상이 오름차순(또는 일정한 순서로) 정렬되어 있어야 함

 

🔧 기본 동작 방식 (코드 설명 포함)

예시: 정렬된 배열 arr = [1, 3, 5, 7, 9, 11] 에서 숫자 7 을 찾고 싶을 때

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

 

💡 언제 사용하는가?

1. 정렬된 배열/리스트에서 특정 값 찾기

• 전형적인 이진탐색 사용처
• 예: N개의 숫자 중 특정 숫자 존재 여부 확인, 특정 위치 찾기

2. 탐색 대상이 "답"일 수 있을 때 — 결정 문제

• 이진탐색의 고급 활용!
• 예시 상황:
  • 최솟값/최댓값 구하기
  • 조건을 만족하는 가장 작은 값 찾기
  • 이분 탐색의 탐색 대상이 값 자체인 경우
• 📌 주로 Parametric Search (매개변수 탐색) 이라고 부르기도 함

예제 문제들:

문제 유형	설명
🎯 정수 찾기	정렬된 배열에 x가 존재하는지 O(log N)으로 판단
🎯 나무 자르기	"길이 H로 자르면 나무 길이 합이 M 이상인가?" → 조건 만족하는 최소 H 찾기
🎯 배 배치하기	"최소 거리 D로 배치 가능한가?" → 최대의 최소 거리 D 구하기
🎯 특정 조건 만족하는 최솟값/최댓값 구하기	이분탐색 대상이 값 자체 (거리, 시간, 용량 등)

 

📌 정리

구분	내용
조건	정렬된 리스트, 혹은 "조건을 만족하는 값"을 찾는 문제
시간복잡도	O(log N)
자주 쓰이는 상황	정수 존재 확인, 결정 문제, 범위 탐색 문제
고급 활용	파라메트릭 서치(최소/최대값 찾기), lower/upper bound