[알고리즘] 재귀함수(Recursive Function)를 활용한 이진탐색(Binary Search) using by Python

(1) 정렬된 리스트가 주어진다.

(2) 찾고자 하는 원소들을 담은 리스트가 주어진다.

(3) 찾고자 하는 원소들이 각각 리스트에서 몇 번째에 위치한 숫자인지 출력하는 프로그램

 

Input

(1) : 1 2 3 4 5
(2) : 1 3 6

 

Output

0 2 -1

 

# Binary Search

# Python

def binaray_search(l, left, right, val):
    mid = (left + right) // 2
    

    # 찾는 값이 없는 경우
    if left == right and l[mid] != val:
        return -1

    # 중앙 값이 찾는 값일 경우
    if l[mid] == val:
        return mid

    # 찾는 값이 왼쪽 리스트에 있을 경우
    elif l[mid] > val:
        return binaray_search(l, left, mid, val)
    # 찾는 값이 오른쪽 리스트에 있을 경우
    else:
        return binaray_search(l, mid+1, right, val)

 

l = list(map(int, input().split()))

f = list(map(int, input().split()))

 

for i in f:
    print(check(l, 0, len(l) - 1, i))