이진 탐색 편집하기

'''이진 탐색'''(Binary Search)은 정렬된 배열에서 원하는 값을 효율적으로 찾는 탐색 알고리즘이다.  이진 탐색은 탐색 범위를 절반씩 줄여 O(log n)의 시간 복잡도를 가진다.
==알고리즘 개요==
*정렬된 배열에서만 적용 가능하다.
*탐색 범위를 절반씩 줄이며, 중간 값을 기준으로 비교한다.
==이진 탐색 과정==
#배열의 중간 요소를 선택한다.
#찾고자 하는 값과 비교한다.
#같다면 탐색 종료, 다르면 왼쪽 또는 오른쪽 절반을 선택하여 반복한다.
==이진 탐색 슈도코드==
<pre>
BinarySearch(array, target):
    low = 0
    high = length(array) - 1

    while low ≤ high:
        mid = (low + high) // 2
        if array[mid] == target:
            return mid  # 값 찾음
        elif array[mid] < target:
            low = mid + 1  # 오른쪽 탐색
        else:
            high = mid - 1  # 왼쪽 탐색

    return -1  # 값 없음
</pre>
==이진 탐색 파이썬 코드==
'''반복문 기반 이진 탐색'''<syntaxhighlight lang="python">
def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 값 찾음
        elif arr[mid] < target:
            low = mid + 1  # 오른쪽 탐색
        else:
            high = mid - 1  # 왼쪽 탐색

    return -1  # 값 없음
</syntaxhighlight>'''재귀 기반 이진 탐색'''<syntaxhighlight lang="python">
def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1  # 값 없음

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)
</syntaxhighlight>
==시간 복잡도==
*'''최선의 경우 (Best Case):''' O(1) (찾고자 하는 값이 처음 선택한 중간 값일 경우)
*'''평균 및 최악의 경우 (Average & Worst Case):''' O(log n)
==이진 탐색의 응용==
*'''정렬된 데이터에서 탐색'''
**데이터베이스 및 검색 엔진 최적화.

*'''이진 검색 트리 (BST)'''
**트리 구조에서 효율적인 검색을 수행.

*'''결정 문제 해결'''
**특정 조건을 만족하는 최적의 값을 찾는 데 사용 (예: 파라메트릭 서치).
==같이 보기==
*[[선형 탐색]]
*[[이진 검색 트리]]
*[[분할 정복 알고리즘]]
*[[점프 탐색]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press.
[[분류:알고리즘]]
[[분류:자료 구조]]