TIL 9. 이진탐색, 재귀함수

이진탐색과 재귀함수에 대해 알아보자.

이진탐색

이진탐색은 업다운 게임과 비슷하다.
정렬되어있지 않으면 쓸모가 없다.

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):
    for number in array:
        if target == number:
            return True

    return False


result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

위는 하나하나 비교하면서 찾는 코드.
아래는 이진함수로 찾는 코드

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)

재귀함수

재귀함수는 함수내에서 다시 해당 함수를 호출한다.

def countdown(number):
    if number < 0:   
        return

    print(number)          
    countdown(number - 1)

countdown(60)
#60
#59
#58
#...
#57

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))
# 120