Python: 이진 검색 알고리즘 🔎

소개

이 문서의 목적은 이진 검색 알고리즘과 작동 방식을 설명하는 것입니다. 그런 다음 직접 작성하는 방법을 배울 수 있도록 Python에서 이진 검색의 예를 살펴보겠습니다.

이진 검색이란 무엇입니까?

이진 검색은 정렬된 배열 내에서 대상 값의 위치를 ​​찾는 검색 알고리즘입니다. 실행시간복잡도가 O(log2N)인 가장 효율적인 탐색 알고리즘이다. 이진 검색은 작은 배열을 제외하고는 선형 검색보다 빠릅니다. Divide and Conquer 알고리즘으로 간주됩니다. 이진 검색보다 더 효율적으로 검색할 수 있는 해시 테이블과 같이 빠른 검색을 위해 설계된 특수 데이터 구조가 있습니다. 그러나 이진 검색은 배열에 없는 경우에도 대상을 기준으로 배열에서 다음으로 작은 요소 또는 다음으로 큰 요소를 찾는 것과 같이 더 넓은 범위의 문제를 해결하는 데 사용할 수 있습니다.

어떻게 작동합니까?

이진 검색은 배열의 middle_index를 target_number와 비교하여 시작합니다. target_number가 middle_index와 일치하면 배열에서 해당 위치가 반환됩니다.

일치하지 않으면 알고리즘은 target number가 greater than인지 less than가 middle_index인지 결정합니다. 배열이 정렬되었으므로 target_number가 배열의 왼쪽(lower) 절반에 있는지 또는 오른쪽(upper) 절반에 있는지 결정합니다.

효과적인 알고리즘divided the problem in half . target_number를 포함하지 않는 것으로 알고 있는 어레이의 절반을 "배제"합니다.

It Repeat the same process , 새로운 절반 크기 배열의 middle_index에서 시작합니다. 이 프로세스는 알고리즘이 target_number를 찾거나 전체 세트를 "배제"할 때까지 반복해서 반복됩니다.

Python에서 이진 검색 구현

Python을 사용하여 이진 검색을 구현하는 방법을 살펴보겠습니다. 아래 의사 코드는 각 코드 줄에 대해 수행된 단계를 설명하는 데 도움이 됩니다.

의사 코드

low_index 및 middle_index를 정의합니다.

while 루프를 시작합니다.

정의middle_index .

target_number가 middle_index와 같으면 True를 반환합니다.

target_number가 middle_index보다 작은 경우
그러면 high_index는 middle_index - 1가 됩니다.

target_number가 middle_index보다 큰 경우
그러면 low_index는 middle_index + 1가 됩니다.

NO target_number 이면 False 를 반환합니다.

def binary_search(lst, target_number):
    """Binary Search Algorithm"""
    # 1. Define low_index & high_index:
    low_index = 0
    high_index = len(lst) - 1

    # 2. Start while loop:
    while low_index <= high_index:
        # 3. Define middle_index:
        middle_index = (low_index + high_index) // 2
        # 4. If target_number == middle_index, then return True:
        if target_number == lst[middle_index]:
            return True
        # 5. If target_number is less than middle_index,
        # then high_index becomes middle_index - 1:
        elif target_number < lst[middle_index]:
            high_index = middle_index - 1
        else:
            # 6. If target_number is greater than middle_index,
            # then the low_index-index becomes middle_index:
            low_index = middle_index + 1
    # 7. If NO target_number, then return False:
    return False

결론

이 기사에서는 이진 검색 알고리즘의 작동 방식과 Python을 사용하여 이를 구현하는 방법에 대해 설명했습니다. 알고리즘 작동 방식을 더 잘 이해하고 자신만의 변형을 작성할 수 있기를 바랍니다. 이 글이 도움이 되셨거나 질문이 있으시면 댓글을 남겨주세요.


GitHub에서 사용 가능한 코드