바이너리 검색 - Binary Search

첫 번째 프로그래밍을 건드리면 몇 가지 알고리즘을 건드릴 것입니다.

그 중 가장 먼저 배우는 것이 데이터 처리 과정에서 자주 사용되는 바이너리 검색(Binary Search)이다.

그렇다면 바이너리 검색이란 무엇입니까?

바이너리 검색 (Binary Search)

이진 검색은 주어진 배열에서 원하는 값을 신속하게 찾는 알고리즘이며,

바이너리 검색의 작동 방식

이동하려는 배열의 중앙값 선택
선택한 값과 원하는 값의 비교
선택한 값이 원하는 값과 같으면 탐색을 종료하고 값을 반환합니다.
선택한 값이 원하는 값보다 큰 경우 선택한 값의 왼쪽 부분 배열에서 1-3단계를 반복합니다.
선택한 값이 원하는 값보다 작으면 선택한 값의 오른쪽 부분 배열에서 1-3단계를 반복합니다.

이와 같이 반복하면서 탐색 범위를 반으로 줄이면서 원하는 값을 찾을 수 있다.

바이너리 검색의 장점은 배열의 크기가 매우 크거나 검색을 반복해야 하는 경우,

탐색 속도가 매우 빠르다는 점.

또한 배열이 정렬되어야 한다는 제약이 있지만,

정렬하면 최악의 경우에도 O (log n)의 시간 복잡도가 있기 때문에

다른 검색 알고리즘보다 빠르게 작동합니다.

이제 파이썬에서 예제를 살펴 보겠습니다.

덧붙여서, 파이썬에서는 bisect_left() 함수를 작성하고 쉽게 찾을 수 있지만,이 예제에서는 bisect_left() 함수를 사용하지 않았습니다.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr(mid) == target:
            return mid
        elif arr(mid) > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

arr = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
target = 7

result = binary_search(arr, target)

if result !
= -1:
    print(f"Value {target} is present at index {result}")
else:
    print(f"Value {target} is not present in the list")

바이너리 검색 – Binary Search

바이너리 검색 (Binary Search)

인기글

바이너리 검색의 작동 방식