[알고리즘 기초] 이진 검색 Binary Search

이진 탐색은 정렬된 리스트나 배열에서 목표 요소를 효율적으로 찾기 위해 사용되는 검색 알고리즘입니다. 이 알고리즘은 검색 간격을 반으로 계속 나누어가며 중간 요소를 목표와 비교합니다. 만약 중간 요소가 목표와 같다면 검색은 성공적으로 끝나고, 알고리즘은 목표 요소의 인덱스를 반환합니다. 만약 중간 요소가 목표보다 크다면, 검색은 리스트의 왼쪽 절반에서 계속됩니다. 만약 중간 요소가 목표보다 작다면, 검색은 리스트의 오른쪽 절반에서 계속됩니다. 이 과정은 목표 요소를 찾거나 검색 간격이 비어있을 때까지 반복됩니다.

이제 파이썬으로 이진 탐색을 구현해 보겠습니다:

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

# 예제 사용:
nums = [0, 2, 2, 3, 4, 4, 7, 7, 7, 9, 10]  # 리스트가 정렬되어 있어야 합니다.
targetNum = 7
result = binary_search(nums, targetNum)

if result != -1:
    print(f"목표 숫자 {targetNum}은(는) 인덱스 {result}에 있습니다.")
else:
    print(f"목표 숫자 {targetNum}은(는) 리스트에 존재하지 않습니다.")

이 파이썬 코드에서 binary_search 함수는 두 개의 인자를 받습니다. arr은 정렬된 리스트이고 target은 찾으려는 요소입니다. 함수는 두 개의 포인터인 left와 right를 초기화하여 검색 간격을 나타냅니다. 이 포인터들은 초기에는 리스트 전체를 커버하도록 설정됩니다.

함수는 left 포인터가 right 포인터보다 작거나 같을 때까지 while 루프에 진입합니다. 루프 내에서는 mid 인덱스를 계산하여 left와 right의 평균으로 설정합니다. 이 때, 결과는 가장 가까운 정수로 내림됩니다.

그 후, mid 인덱스의 요소를 목표 요소와 비교합니다. 만약 같다면, 함수는 mid 인덱스를 반환하여 목표 요소를 찾았음을 나타냅니다.

만약 mid 인덱스의 요소가 목표보다 작다면, 검색은 리스트의 오른쪽 절반에서 계속됩니다. 이 때 left 포인터를 mid + 1로 갱신합니다.

만약 mid 인덱스의 요소가 목표보다 크다면, 검색은 리스트의 왼쪽 절반에서 계속됩니다. 이 때 right 포인터를 mid - 1로 갱신합니다.

이러한 과정은 목표 요소를 찾거나 검색 간격이 비어있을 때까지 반복됩니다. 만약 목표 요소가 리스트에 없다면, 함수는 -1을 반환합니다.

예제 사용 부분에서는 정렬된 숫자들의 리스트(nums)와 targetNum이 7인 경우를 보여줍니다. 목표 숫자 7은 리스트에서 여러 번 나타나므로, 알고리즘은 첫 번째 등장하는 인덱스를 반환할 것입니다. 따라서 출력은 다음과 같을 것입니다:

목표 숫자 7은(는) 인덱스 6에 있습니다.

목표 숫자가 리스트에 없다면 출력은 다음과 같았을 것입니다:

목표 숫자 7은(는) 리스트에 존재하지 않습니다.