재귀함수를 통한 이진탐색

정렬이 되어있는 배열을 탐색하는 함수입니다. 재귀함수를 이용한 이진탐색으로 찾는 수가 있으면 "값이 있습니다"를 출력하고 없을 경우 "값이 없습니다"를 출력합니다.

​

작동원리

1. 배열과 찾을 값을 입력받습니다.

2. 배열의 중간값과 찾을 값을 비교한다.

3. 두 값이 같을 경우 "값이 있습니다"를 출력하고 중간값이 찾을 값보다 큰 경우 중간이전까지로 중간값이 더 작은 경우 중간이후까지로 구간을 변경하여 1번부터 반복합니다.

4. 만약 구간이 1밖에 남지 않았는데 값을 찾지 못한 경우 "값이 없습니다"를 출력합니다.

​

소스코드

def bs(array, num):
    value = array[int(len(array) / 2)]
    if len(array) == 1 and value != num:
        print("값이 없습니다.")
        return 0
    if value == num:
        print("값이 있습니다.")
        return 0
    else:
        if value > num:
            bs(array[0:int(len(array)/2)], num)
        else:
            bs(array[int(len(array)/2):len(array)+1], num)