[Algorithm🧬] 정올 1295 : 이진 탐색

문제

import sys

def binary_search(start, end, find, arr):
    if start > end:
        return -1

    mid = (start + end) // 2

    if arr[mid] == find:
        return mid
    elif arr[mid] < find:
        return binary_search(mid + 1, end, find, arr)
    else:
        return binary_search(start, mid - 1, find, arr)


# 입력 처리
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

find_n = int(sys.stdin.readline())
find_arr = list(map(int, sys.stdin.readline().split()))

for i in range(find_n):
    print(binary_search(0, n - 1, find_arr[i], arr) + 1)

이진 탐색은 기억 나는데

1. return binary_search 안하고 그냥 binary_search 부르는 재귀 만들었다가 출력이 너무 많이 찍혀서 놀라고
2. mid + 1 로 출력했더니 start, end 조건 안맞아서 또 많이 출력돼서 놀라고...

진짜 내 지식 다 어디로 사라졌니...

재귀 말고 그냥 반복문으로 푸는 법

def binary_search(find):
    left = 0
    right = n - 1

    while left <= right:
        mid = (left + right) // 2

        if num[mid] == find:
            return mid + 1
            break
        elif num[mid] > find:
            right = mid - 1
        else:
            left = mid + 1

    return 0

for q in query:
    print(binary_search(q))