[Python] 이분 탐색

이분 탐색 알고리즘

 

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))

#1 중간 위치를 찾는다.

#2 찾는 값과 중간 값을 비교한다.

#3 같다면 위치번호를 돌려주고

#4 찾는 값이 중간 값보다 크면 중간 위치의 오른쪽을 대상으로 다시 탐색(1번부터 다시)

#5 찾는 값이 중간 값보다 작다면 중간 위치의 왼쪽을 대상으로 다시 탐색(1번부터 다시)