이진탐색(재귀)

문제 정의

정렬된 리스트와 찾고자 하는 숫자 리스트가 입력되었을 때, 찾고자 하는 숫자가 각각 리스트에서 몇 번째에 위치한 숫자인지 출력하는 프로그램을 작성하세요.
Hint

리스트의 각 원소를 한 줄에 출력하기 위해서는 다음과 같이 실행하면 됩니다.
l = [1,2,3,4]
print(*l)

출력 결과: 1 2 3 4

입력 형식

입력의 첫 줄에 테스트 케이스의 숫자 t가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 n(n≤100,000)개의 숫자 리스트가 띄어쓰기로 구분되어 입력된다.
다음 줄에는 찾고자 하는 m(m≤100,000)개의 숫자 리스트가 입력된다.
각 테스트 케이스의 첫 번째 리스트에 있는 숫자는 모두 다르며 정렬되어 있다.

출력 형식

각 테스트 케이스에 대해 찾고자 하는 숫자가 리스트에 있다면 몇 번째인지(0부터 시작) 출력하고, 리스트에 없다면 -1을 출력하라.
각 테스트 케이스의 출력은 한 줄에 이루어져야한다.

입력 예제

3
1 2 3 4 5
1 3 6
1 3 5 7
2 3 6
2 3 4 5 6
5 3 1

출력 예제

0 2 -1
-1 1 -1
3 1 -1

t = int(input())

def binary_search (li, find, start, end):
    if start > end:
        return -1
    mid = (start + end)//2
    if li[mid] == find:
        return mid
    elif li[mid] < find:
        return binary_search(li, find, mid+1, end)
    else:
        return binary_search(li, find, start, mid-1)

for _ in range(t):
    ans = []
    l = list(map(int, input().split()))
    s = list(map(int, input().split()))
    for i in s:
        ans.append(binary_search(l, i, 0, len(l)-1))

    print(*ans)