이진 검색 알고리즘의 Python 상세 분석

이 글은 python에 대한 관련 지식을 제공합니다. 알고리즘 설명, 알고리즘 분석, 알고리즘 아이디어 등 이진 검색 알고리즘과 관련된 문제를 주로 정리합니다. 함께 살펴보는 것이 도움이 되기를 바랍니다. 모두가 도움이 됩니다.

추천 학습: 파이썬 동영상 튜토리얼

1. 알고리즘 설명

이분법은 비교적 효율적인 검색 방법입니다

전에 했던 숫자 추측 게임을 떠올려 미리 정해진 A를 줍니다. 100보다 작은 양의 정수 x를 추측하면 크기를 판단하는 데 도움이 됩니다. 어떻게 빨리 추측할 수 있나요?

저희가 이전에 만든 게임에서는 이진 탐색 방법을 배우면 , 아니오. 숫자가 무엇이든 상관없이 숫자를 추측하는 데는 최대 7번만 걸립니다.

2. 알고리즘 분석

1. 순서가 있는 시퀀스여야 합니다.

2. 데이터 양에 대한 요구 사항이 있습니다.

데이터 양이 너무 적고 이진 검색에 적합하지 않습니다. 직접 순회에 비해 효율성 향상이 뚜렷하지 않습니다.

데이터의 양이 너무 많으면 배열에 지속적인 저장 공간이 필요하기 때문에 이진 검색을 사용하는 것은 적합하지 않습니다. 데이터의 양이 너무 많으면 이러한 대규모 데이터를 저장할 연속적인 메모리 공간을 찾지 못하는 경우가 많습니다. . .

3. 알고리즘 아이디어

다음과 같은 순서가 있는 목록이 있다고 가정합니다.



이 목록에 있는 숫자 11은 무엇인가요?

4. 구현

순수한 알고리즘 구현

구현 코드:

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]# 需要查找的数字seek_number = 11# 保存一共查找了几次count = 0# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1# 当左侧索引小于等于右侧索引时while left  arr_list[middle]:
        # 左侧索引为中间位置索引+1
        left = middle + 1
    # 如果查找的数字小于中间位置的数字时
    elif seek_number <p>실행 결과: </p><p><img src="https://img.php.cn/upload/article/000/000/067/ab7ca007166584d2196443b3030f239a-4.png" alt="이진 검색 알고리즘의 Python 상세 분석"></p><h2>재귀적 메서드 구현</h2><blockquote><p>첫 번째 루프 이후에 개수가 변경되지 않으면 변수 개수가 정의된다는 의미입니다. 이때 입력은 순서가 있는 시퀀스이므로 루프를 종료하기 위해 직접 반환됩니다. 이때의 시간 복잡도는 O(n)</p></blockquote><p>구현 코드: </p><pre class="brush:php;toolbar:false">arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]def binary_search(seek_number, left, right):
    if left  arr_list[middle]:
            left = middle + 1
        else:
            return middle        # 进行递归调用
        return binary_search(seek_number, left, right)
    # 当左侧索引大于右侧索引时，说明没有找到
    else:
        return -1# 查找的数字seek_number = 11# 列表左侧索引left = 0# 列表右侧索引right = len(arr_list) - 1print("查找的数字：%s，索引为：%s" % (seek_number, binary_search(seek_number, left, right)))

실행 결과:

권장 학습 : 파이썬 비디오 튜토리얼

위 내용은 이진 검색 알고리즘의 Python 상세 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!