[Algorithm] 이진 탐색 (python)

이진 탐색

이진 탐색은 탐색 시, 범위를 반으로 좁혀가며 탐색하는 것을 의미한다.

1~16범위의 배열이 있고 '14'를 탐색하는 상황

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

def is_existing_target_number_binary(target, array):
    # 구현해보세요! (이진 탐색)
    current_min = 0                 # 최소값
    current_max = len(array) - 1    # 최대값
    current_guess = (current_min + current_max) // 2    # 중위값

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            # 최소값을 변경
            current_min = current_guess + 1
        else:
            # 최대값을 변경
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2
    return False

result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

• 탐색을 하기위해 범위를 설정한다 (인덱스값을 바탕으로 탐색)
  • 최소값, 최대값 인덱스를 정하고, 범위를 반으로 좁혀가며 탐색하도록

[출력]
True

시간복잡도

• O(log n)
  • 데이터 범위를 반으로 좁혀가며 탐색을 하기 때문에, 한 번 동작할 때마다 탐색 범위가 절반으로 줄어든다
  • 연산량이 반으로 줄어들면 O(log n)

주의할 점은, 이진 탐색은 정렬된 상태의 데이터일때만 가능하다.
정렬되어 있지 않은 데이터에서 이진 탐색을 사용하면, 원하는 동작이 이루어지지 않는다