UNIT 10 (탐색)

이분 탐색

문제) 자료의 크기 순서대로 정렬된 리스트에서 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘을 만들어라. 리스트에 찾는 값이 없으면 -1을 돌려준다.

#리스트에서 특정 숫자 위치 찾기(이분 탐색)
#입력 : 리스트 a, 찾는 값 x
#출력 :  찾으면 그 값의 위치, 찾지 못하면 -1

def binary_search(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2
        if x == a[mid]:
            return mid
        elif x > a[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return -1


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))
print(binary_search(d, 50))

#계산 복잡도 = O(log n)

연습문제

10-1) 다음 과정을 참고하여 재귀 호출을 사용한 이분 탐색 알고리즘을 만들어라.
(1) 주어진 탐색 대상이 비어 있다면 탐색할 필요가 없다(종료 조건).
(2) 찾는 값과 주어진 탐색 대상의 중간 위치 값을 비교한다.
(3) 찾는 값과 중간 위치 값이 같다면 결과값으로 중간 위치 값을 돌려준다.
(4) 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽 대상으로 이분 탐색 함수를 재귀 호출한다.
(5) 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽을 대상으로 이분 탐색 함수를 재귀 호출한다.

#리스트에서 특정 숫자 위치 찾기 (이분 탐색과 재귀 호출)
#입력 : 리스트 a, 찾는 값 x
#출력 : 특정 숫자를 찾으면 그 값의 위치, 찾지 못하면 -1

def binary_search_sub(a, x, start, end):
    if start > end:
        return -1

    mid = (start + end) // 2
    if x == a[mid]:
        return mid
    elif x > a[mid]:
        return binary_search_sub(a, x, mid + 1, end)
    else:
        return binary_search_sub(a, x, start, mid - 1)

    return -1


def binary_search(a, x):
    return binary_search_sub(a, x, 0, len(a) - 1)


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))
print(binary_search(d, 50))

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10