[1028알고리즘 16]이진탐색 vs 순차탐색

이진 탐색 알고리즘의 장점

• 선형 탐색과 비교하여 탐색 시간이 빠르다. (선형 탐색의 경우 시간 복잡도는 T(n) = θ(n)이다. ) 이진 탐색 알고리즘의 단점
• 정렬된 리스트에서만 사용될 수 있다.

순차탐색의 시간복잡도는 O(n)

이진탐색의 시간복잡도는 O(logN)

 

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_Sequential(target, array):
    find_count = 0
    for idx in range(len(finding_numbers)):
        find_count += 1
        if finding_numbers[idx] == finding_target:
            print(find_count)
            return True
    return False


def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    find_count = 0
    while current_min <= current_max:
        find_count += 1
        if array[current_guess] == target:
            print(find_count)
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_max + current_min) // 2

    return False


print(is_existing_target_number_Sequential(finding_target, finding_numbers))
print(is_existing_target_number_binary(finding_target, finding_numbers))