[파이썬] 이진검색 알고리즘(binary search algorithm)

이진 검색 알고리즘(binary search algorithm)은

오름차순으로 정렬된 리스트에서

특정한 값의 위치를 찾는 알고리즘 입니다.

간략한 방법은 첫음부터 찾는 것이 아니라 데이터의 중간을 찾아서 찾고자하는 값과 비교해서

중간이 작으면 오른쪽으로 이동 (오름차순 정렬이니까 중간이 작으면 오른쪽에 찾고자 하는 값이 있겠죠),

중간이 크면 왼쪽으로 이동하면서 (오른차순 정렬이니까 중간이 크면 왼쪽에 찾고자 하는 값이 있겠죠)

계속 중간을 찾아 비교하면서 찾습니다.

속도가 빠른 장점이 있습니다.

 

def binary_search(a, left, right, K):
    if right >= left:              # 
        mid = (left + right) // 2  # 중간 인덱스를 찾습니다. '//'는 나누기의 몫 연산자 입니다.
        if a[mid] == K:            # 데이터(리스트)의 인덱스가 가리키는 값이 찾는 값과 같으면 True(찾음)
            return True
        elif a[mid] > K:           # 찾는 값 보다 인덱스가 가리키는 값이 크면
            return binary_search(a, left, mid - 1, K)   # right가 mid-1이 됨. 왼쪽으로 감.
        else:                      # 찾는 값 보다 인덱스가 가리키는 값이 작으면
            return binary_search(a, mid + 1, right, K)  # left가 mid+1 이 됨. 오른쪽으로 감.
    else:
        return False               # 찾는 값이 없음
    

input_list = [10, 20, 25, 35, 45, 55, 60, 75, 85, 90]

n = len(input_list)
print('55 탐색:', binary_search(input_list, 0, n-1, 55))   # 55를 찾음. True
print('50 탐색:', binary_search(input_list, 0, n-1, 50))   # 50을 찾음. Flase