9. 이진 탐색 (Binary Seach)

9. 이진 탐색 (Binary Seach)

1. 이진 탐색이란?

• 정렬된 리스트에서 특정 값을 빠르게 찾는 방법
• 전체를 처음부터 끝까지 뒤지지 않고, 중간을 기준으로 반씩 줄여나가는 방식

💡 동작 방식: “반 갈라서 쳐내기”

예: 정렬된 리스트가 있다고 가정해보자

[1, 3, 5, 7, 9, 11, 13]

9를 찾고 싶다면

1. 중간값 → 7 → 작으니 오른쪽 절반만 보기
2. 그다음 중간 → 11 → 크니 왼쪽 절반만 보기
3. 찾음!

총 3번 비교만으로 찾음

시간복잡도 O(log N) (매 단계마다 절반씩 날려버림)

---

2. 이진 탐색 기본 구조

반복문

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]
print(binary_search(arr, 11))


''' 출력
5
'''

재귀

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)

---

3. 라이브러리

파이썬에선 bisect 라이브러리로 간단하게 구현 가능

import bisect

arr = [1, 3, 5, 7, 9]
idx = bisect.bisect_left(arr, 5) # 5 위치
print(idx) 


''' 출력
2
'''

---

4. 이진 탐색은 어디에 쓰나?

분야	설명
값 찾기	특정 숫자가 리스트에 존재하는지
위치 찾기	특정 조건을 만족하는 값의 최소/최대 인덱스
개수 세기	정렬된 리스트에서 특정 값의 등장 횟수
최적화 문제	이진탐색 범위를 “값 자체”로 잡는 경우 (parametric search)