이진 탐색(Binary Search)

이진 탐색

"정렬된 리스트에서 중간 값을 기준으로 범위를 좁혀가며 탐색하는 알고리즘"

• 탐색할 때마다 범위를 절반으로 줄이므로 매우 빠름
• 시간복잡도: O(log n) (탐색 범위가 계속 반으로 줄어듦)
• 정렬된 데이터에서만 사용할 수 있음! (정렬이 안 되어 있으면 사용 불가)

---

이진 탐색 동작 원리

리스트가 정렬되어 있어야 한다.

1. 중간 값을 기준으로 찾고자 하는 값과 비교
2. 찾는 값이 중간 값보다 작으면 왼쪽으로, 크면 오른쪽으로 탐색 범위 축소
3. 이 과정을 반복하여 값을 찾음

# Pseudo Code
FUNCTION BinarySearch(arr, target)
    left = 0
    right = length(arr) - 1

    WHILE left ≤ right DO
        mid = (left + right) / 2  # 중간 값 찾기
        
        IF arr[mid] == target THEN
            RETURN mid  # 찾으면 인덱스 반환
        
        ELSE IF arr[mid] < target THEN
            left = mid + 1  # 오른쪽 범위로 이동
        
        ELSE
            right = mid - 1  # 왼쪽 범위로 이동
    END WHILE

    RETURN -1  # 찾지 못하면 -1 반환
END FUNCTION


# Full Code
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  # 찾지 못하면 -1 반환


# 테스트
arr = [2, 3, 5, 7, 8, 10, 12, 15, 18]
target = 7
result = binary_search(arr, target)

print(f"찾는 값 {target}의 위치: {result}" if result != -1 else "값을 찾을 수 없음")

---

이진 탐색의 시간복잡도

경우	시간복잡도
최선 (첫 번째 시도에서 찾음)	O(1)
평균	O(log n)
최악 (값이 없거나 마지막에 찾음)	O(log n)

 

✅ 탐색할 때마다 범위가 절반으로 줄어듦 O(log n)
✅ 정렬이 되어 있다면 선형 탐색(O(n))보다 훨씬 빠름

---

이진 탐색의 장단점

장점

 

• 탐색 속도가 빠름 (O(log n)) 
• 대량의 데이터에서도 사용 가능
• 반복문, 재귀 방식으로 간단하게 구현 가능

단점

 

• 정렬된 데이터에서만 사용 가능
• 데이터 삽입/삭제가 빈번한 경우 비효율적
• 연결 리스트에서는 비효율적

결론

이진 탐색은 O(log n)의 빠른 속도를 제공하지만, 반드시 정렬된 데이터에서만 사용할 수 있다. 삽입/삭제가 빈번한 경우는 해시 테이블이 더 적합하다.