이진 검색은 정렬된 숫자 배열에서 특정 숫자를 찾는 알고리즘입니다. 배열을 둘로 나누어 중간 값을 확인하고, 찾고자 하는 숫자가 중간 값보다 작으면 왼쪽 부분 배열을, 크면 오른쪽 부분 배열을 탐색합니다. 이 과정을 반복하여 원하는 숫자를 찾을 때까지 계속 진행합니다.

이진 검색 알고리즘

다음은 파이썬으로 구현된 이진 검색 알고리즘의 예시 코드입니다.

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

사용 예시

이진 검색 알고리즘을 사용하여 배열에서 특정 숫자를 찾는 예시입니다.

arr = [1, 3, 5, 7, 9, 11]
target = 7

result = binary_search(arr, target)
if result != -1:
    print(f"찾는 숫자 {target}는 인덱스 {result}에 위치합니다.")
else:
    print("찾는 숫자가 배열에 존재하지 않습니다.")

위의 예시 코드를 실행하면, 배열 [1, 3, 5, 7, 9, 11]에서 숫자 7을 찾아 인덱스 3에 위치한다는 결과가 출력됩니다.

시간 복잡도

이진 검색 알고리즘의 시간 복잡도는 O(log n)입니다. 배열을 이분하여 탐색하는 방식이기 때문에 탐색 범위가 빠르게 절반씩 줄어들게 되어 효율적인 검색이 가능합니다.

결론

이진 검색은 정렬된 배열에서 특정 숫자를 효율적으로 찾는 알고리즘입니다. 이를 이용하여 큰 데이터셋에서 원하는 값을 빠르게 찾을 수 있습니다. 그러나 이진 검색을 사용하기 위해서는 배열이 정렬되어 있어야 한다는 전제 조건이 있습니다.