[알고리즘][python]이진탐색 (재귀로 구현!)

강의 링크

(이코테 2021 강의 몰아보기) 5. 이진 탐색

이진 탐색 정의

입력으로 정렬된 리스트가 주어지고, target이 주어진다. 우리는 정렬된 리스트에서 target을 찾아야한다.
ex) 리스트 1 2 3 4 5 6 7 8 9 10, target = 3

간단하게 설명하자면 start와 end를 맨 끝으로 잡고 그 중간인 mid를 설정한다.
이때 start, end, mid 모두 인덱스를 뜻한다.
예를들어 start가 0이고, end가 9일때 mid = 4.5인데 대부분의 경우 소수점을 버린다.

다음 mid와 target을 비교해서 mid가 더 크면 mid이상의 리스트 부분은 안봐도 되니까 end를 mid -1 로 다시 설정해서 다시 탐색을 하고,

혹은, mid가 더 작으면 mid이하의 리스트 부분은 안봐도 되니까 start를 mid + 1로 다시 설정해서 다시 탐색을 하면 된다.

이렇게 탐색을 해 나가다가, mid = target이 되면, 탐색이 성공한거다.

만약, start가 end보다 커져버리면 해당 리스트에 target이 존재하지 않는다는 의미다.

간략하게 그려봤다.

파이썬 코드로 이진탐색 구현

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    if array[mid] == target:
        return mid

    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)


n, target = map(int, input().split())

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

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)