Analyse détaillée Python de l'algorithme de recherche binaire

Cet article vous apporte des connaissances pertinentes sur python Il organise principalement les problèmes liés à l'algorithme de recherche binaire, y compris la description de l'algorithme, l'analyse de l'algorithme, les idées d'algorithme, etc. vous. Tout le monde est utile.

Apprentissage recommandé : Tutoriel vidéo Python

1. Description de l'algorithme

La méthode de dichotomie est une méthode de recherche relativement efficace

Rappelez-vous le jeu de devinettes auquel vous avez joué auparavant et donnez-en un prédéterminé A positif un entier x inférieur à 100 vous permettra de deviner et vous donnera des conseils pour juger la taille. Comment pouvez-vous le deviner rapidement

Le jeu que nous avons créé auparavant donnait 10 chances si nous apprenons la méthode de recherche binaire, quelle que soit la valeur. le nombre est, il suffit de 7 fois pour deviner le nombre.

2. Analyse de l'algorithme

1.

2. Il existe des exigences concernant la quantité de données.

La quantité de données est trop petite et ne convient pas à la recherche binaire. Par rapport à la traversée directe, l'amélioration de l'efficacité n'est pas évidente.

Il n'est pas approprié d'utiliser la recherche binaire si la quantité de données est trop importante, car la matrice nécessite un espace de stockage continu. Si la quantité de données est trop importante, l'espace mémoire continu pour stocker des données à si grande échelle n'est souvent pas trouvé. . .

3. Idée d'algorithme

Supposons qu'il existe une liste ordonnée comme suit :



Le numéro 11 est-il dans cette liste ? Implémentation
Implémentation d'algorithme pur

Code d'implémentation :

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 

Résultat d'exécution :

Implémentation de méthode récursive

Un nombre de variables est défini dans la boucle Si le nombre ne change pas après la première boucle, cela signifie. que l'entrée est une séquence ordonnée. À ce moment, nous revenons directement pour sortir de la boucle. La complexité temporelle à ce moment est O(n)

Code d'implémentation :

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)))

Résultats d'exécution :

Apprentissage recommandé. :

Tutoriel vidéo Python

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!