알고리즘 기초 - 이분탐색

 

---

이분탐색?

---

 

 

이분탐색(Binary Search) 은 정렬된 데이터에서 원하는 값을 빠르게 찾는 대표적인 알고리즘입니다.

이분탐색은 정렬된 배열에서만 사용할 수 있는 탐색 기법으로, 탐색 구간을 절반씩 줄여가며 원하는 값을 찾습니다.

 

 

 

---

간단한 과정

---

1. 배열의 중간값(mid) 을 선택한다.
2. 찾는 값과 비교한다
    - 같으면 탐색 종료
    - 찾는 값이 더 크면 오른쪽 구간만 탐색
    - 찾는 값이 더 작으면 왼쪽 구간만 탐색
3. 구간을 계속 절반으로 줄여가며 반복한다.

이렇게 하면 시간 복잡도는 O(logN) 으로, 선형 탐색(O(N))보다 훨씬 빠릅니다.

 

 

예시 : 

배열: [1, 3, 5, 7, 9, 11]
찾는 값: 7

mid = 5 → 7보다 작으므로 오른쪽 탐색
mid = 9 → 7보다 작으므로 왼쪽 탐색
mid = 7 → 찾았다!

 

 

코드

def binary_search_trace(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        print(f"mid = {arr[mid]}", end=" → ")
        
        if arr[mid] == target:
            print("찾았다!")
            return mid
        elif arr[mid] < target:
            print(f"{target}보다 크므로 오른쪽 탐색")
            left = mid + 1
        else:
            print(f"{target}보다 작으므로 왼쪽 탐색")
            right = mid - 1
    
    print("값을 찾을 수 없습니다.")
    return -1


# 실행 예시
arr = [1, 3, 5, 7, 9, 11]
target = 7
idx = binary_search_trace(arr, target)
print("찾은 인덱스:", idx)


#mid = 5 → 7보다 크므로 오른쪽 탐색
#mid = 9 → 7보다 작으므로 왼쪽 탐색
#mid = 7 → 찾았다!
#찾은 인덱스: 3

 

 

활용

이분탐색은 단순히 “값 찾기”에만 쓰이지 않습니다.
조건을 만족하는 최댓값/최솟값을 찾는 최적화 문제에 자주 사용됩니다.

 

주의할 점

• 반드시 정렬된 배열이어야 한다.
• 무한 루프를 방지하려면 left <= right 조건을 주의해야 한다.
• mid 계산 시 (left + right) // 2 를 사용하며, 파이썬에서는 오버플로우 걱정이 없지만 C++/Java에선 (left + right) // 2 대신 left + (right - left) // 2를 권장하기도 한다.

 

 

---

마무리

---

 

이분탐색은 단순한 탐색 알고리즘 같지만, “탐색”을 넘어서 “최적화 문제”를 푸는 강력한 도구입니다.

처음엔 단순히 "중간값을 기준으로 범위를 줄여 나가는 방법"이 전부라고 생각했지만,
직접 코드로 구현해보고, 다양한 문제에 응용되는 모습을 보니 정말 강력한 도구라는 걸 느낄 수 있었습니다.

특히 단순히 "값을 찾는 탐색"에 그치지 않고, 최적화 문제까지 풀 수 있다는 점에서 놀라웠습니다.