IT-garden

이진 탐색(Binary Search)은 리스트를 반으로 나눠 검색하며 원하는 값을 찾는 알고리즘입니다.

원하는 값은 key로 주어지고 탐색의 범위는 low와 high로 주어집니다.

리스트의 중앙에 있는 값을 확인해 찾고자 하는 key 값이 리스트의 중앙에 있는 값보다 작은지 큰지에 따라 검색 범위를 반으로 줄입니다.

- key 값이 리스트의 중간 요소와 일치하면 탐색을 끝냅니다.

- key 값이 리스트의 중간 요소보다 큰 경우 중간 요소 이후의 리스트만 탐색합니다.

- key 값이 리스트의 중간 요소보다 작은 경우 중간 요소 이전의 리스트만 탐색합니다.

이진 탐색을 하기 위해서는 리스트는 반드시 정렬되어 있어야 합니다.

이진 탐색은 이분 탐색이라고도 합니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Binary_Search(key, low, high):

    while low <= high:
        middle = (low + high) //2

        if key == a[middle]:
            return middle

        elif key > a[middle]:
            low = middle + 1
            
        elif key < a[middle]:
            high = middle - 1
        
    return -1
        
# 출력>>6
print(Binary_Search(13, 0, 6))

# 출력>>-1
print(Binary_Search(10, 0, 6))

# 출력>>2
print(Binary_Search(5, 0, 4))

# 출력>>-1
print(Binary_Search(6, 0, 4))

함수 Binary_Search이 이진 탐색 알고리즘입니다.

Binary_Search(13, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key가 13인 인덱스를 찾습니다.

Binary_Search(10, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key가 10인 인덱스를 찾습니다.

Binary_Search(5, 0, 4)

low가 0이고 high가 4입니다. 리스트 a의 인덱스 0에서 4까지에서 key가 5인 인덱스를 찾습니다.

Binary_Search(6, 0, 4)

low가 0이고 high가 4입니다. 리스트 a의 인덱스 0에서 4까지에서 key가 6인 인덱스를 찾습니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Binary_Search(key):
    low = 0
    high = len(a) - 1

    while low <= high:
        middle = (low + high) //2

        if key == a[middle]:
            return middle

        elif key > a[middle]:
            low = middle + 1
            
        elif key < a[middle]:
            high = middle - 1
        
    return -1
        
# 출력>>6
print(Binary_Search(13))

# 출력>>-1
print(Binary_Search(10))

탐색의 범위를 low와 high로 설정하지 않고 리스트 전체에서 key를 찾는 이진 탐색 알고리즘입니다.

가장 많이 사용하는 이진 탐색 알고리즘 코드입니다.

이진 탐색 알고리즘의 시간복잡도는 O(logN)입니다.