이진 탐색 구현하기

이진탐색

이진 탐색은 원하는 값 (target)을 찾기 위해 하나씩 순차적으로 탐색하지 않고, 최솟값과 최댓값을 더해 그것을 2로 나눈 값(반으로 나눈 값)을 구해 그것보다 값이 클 경우 찾는 범위를 더 큰 곳에서 찾아가고, 작은 경우 찾는 범위를 더 작은 곳에서 찾아가면서 반씩 쪼개서 찾는 방식 (up &down게임을 생각하면 쉽다 !! )

이진 탐색의 시간 복잡도는 O(log n)이며, 정렬이 된 데이터들로만 실행할 수 있다.

finding_target = 16
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_max = len(array) - 1
    current_min = 0
    # target을 찾기 위해 추측하고 있는 값은 (최댓값 + 최솟값) // 2를 한 값
    current_guess = (current_max + current_min) // 2
    # 최솟값이 최댓값보다 작거나 같을 때 까지 while문을 돌리면서 탐색한다.
    while current_min <= current_max:
        # 찾고있는 값과 지금 추측하고있는 값이 같다면 바로 True 반환
        if array[current_guess] == target:
            return True
        # 추측하고 있는 값이 찾고 있는 값보다 작다면 최솟값을 
        # 추측값보다 한 칸 앞에서 다시 탐색
        elif array[current_guess] < target:
            current_min = current_guess + 1
        # 추측하고 있는 값이 더 크다면
        # 최댓값을 추측값보다 한칸 뒤에서 다시 탐색
        else:
            current_max = current_guess - 1
        # while문을 다시 돌기 전에 추측 값을 update 해준다.
        current_guess = (current_max + current_min) // 2
    # while문을 다 돌 때 까지 원하는 값을 찾지 못하면 False를 반환
    return False



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

 

16이 배열의 마지막 index에 있으므로 결과로 True를 반환한다.