“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky, and many good programmers have done it wrong the first few times they tried.” — Donald Knuth 번역: 2점 찾기의 기본 사상은 상대적으로 간단하지만 디테일이 매우 까다로울 수 있습니다. 많은 우수한 프로그래머들이 최초의 시도에서 실수를 했습니다.

2분 Binary 검색

알고리즘 사상: 2분 찾기는 n개의 요소를 포함하는 질서정연한 서열에서 목표 값을 효과적으로 포지셔닝하는 데 사용된다.세 가지 상황을 고려해 보자.

목표 값value == [middle]의 데이터가 성공적으로 검색되고 종료된 경우

만약 목표치value > [middle]의 데이터가 후반부 서열에 대해 이 과정을 반복한다면 인덱스의 범위는 mid + 1부터 right까지

만약 목표치value < [middle]의 데이터가 앞부분 서열에 대해 이 과정을 반복한다면 인덱스의 범위는 left부터 middle - 1까지

반복 정의 - Iteratively

# binary_search.py
def binary_search_iterative(elements, value):

    left, right = 0, len(elements)-1

    while left <= right:
        middle = (left + right) // 2

        if elements[middle] == value:
            return middle
        elif elements[middle] < value:
            left = middle + 1
        else:
            right = middle - 1
    return None


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    print(binary_search_iterative(nums, 2))	 # Output: 1, 2 1 （ 0 ）
    print(binary_search_iterative(nums, 10))  # Output: None, ， 

반복 정의 - Recursively

제1판

슬라이스 연산자 : 를 사용하여 목록을 잘라냅니다.

def binary_search_recursive(elements, value):

    if len(elements) == 0:
        return False

    left, right = 0, len(elements) - 1

    if left <= right:
        middle = (left + right) // 2

        if elements[middle] == value:
            return True
        elif elements[middle] < value:
            return binary_search_recursive(elements[middle+1:], value)
        else:
            return binary_search_recursive(elements[:middle], value)

    return False

if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    print(binary_search_recursive(nums, 2))  # True
    print(binary_search_recursive(nums, 10))  # False

반복처럼 while 순환을 사용하지 않고 조건을 검사하기만 하면 된다.대응하는 분할 목록에서 같은 함수를 호출합니다.
분할 필름을 사용하면 어떤 문제가 있습니까?알겠습니다. 슬라이스는 원소가 인용하는 복사본을 생성합니다. 이 복사본들은 현저한 메모리와 계산 비용을 가지고 있을 수 있습니다.

제2판

복사 작업을 피하기 위해 같은 목록을 반복해서 사용할 수 있지만 필요할 때 함수에 다른 경계를 전달할 수 있습니다.

def binary_search(elements, value, left, right):

    if left <= right:
        middle = (left + right) // 2

        if elements[middle] == value:
            return True

        elif elements[middle] < value:
            return binary_search(elements, value, middle+1, right)
        else:
            return binary_search(elements, value, left, middle-1)
    return False

if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    print(binary_search(nums, 2, 0, len(nums)-1))	# True
    print(binary_search(nums, 10, 0, len(nums)-1))	# False

단점은 이 함수를 호출할 때마다 초기 경계를 전달해야 합니다. binary_search(nums, 10, 0, len(nums)-1)

제3판

더 나아가 함수를 다른 함수에 중첩하여 기술적 세부 사항을 숨기고 외부 역할 영역에서 변수를 다시 사용하고자 할 수도 있습니다.

def contains(elements, value):
    def recursive(left, right):
        if left <= right:
            midddle = (left + right) // 2
            if elements[midddle] == value:
                return True
            elif elements[midddle] < value:
                return recursive(midddle+1, right)
            else:
                return recursive(left, midddle-1)
        return False
    return recursive(0, len(elements) - 1)

if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
	print(contains(nums, 2))  # True
    print(contains(nums, 10))  # False

폐쇄된 범위 내에서 recursive() 내부 함수를 정의한 경우에도 요소와 값 매개 변수에 접근할 수 있습니다.
교체와 귀속 실현 사이의 선택은 일반적으로 성능 고려, 편의성, 그리고 개인의 취향의 최종 결과이다.

총결산

본고는 먼저 2분 찾기의 기본 사상을 소개한 다음에 교체와 귀속 두 가지 방법으로 간이판의 2분 찾기를 실현했다. 사실 Python은 기능이 더욱 강한 2분 찾기 라이브러리bisect를 실현했고 흥미를 가진 학생들은 본고를 바탕으로 학습할 수 있다.
마지막: 2분 검색 시간 복잡도: O(log(n))추천 읽기: How to Do a Binary 검색 in Python