Introduction à la recherche binaire et exemples détaillés

Introduction à la recherche binaire

La recherche binaire est également appelée demi-recherche. L'idée de base de la recherche binaire est de supposer que les éléments du dictionnaire sont stockés dans un tableau de manière ordonnée, de petit à petit. large. ,

Comparez d'abord la clé de valeur donnée avec la clé de l'élément au milieu du dictionnaire Si elles sont égales, la récupération est réussie

Sinon, si la clé est. petite, elle sera dans la première moitié du dictionnaire. Continuez la recherche binaire dans la partie

Si la clé est grande, continuez la recherche binaire dans la seconde moitié du dictionnaire.

De cette façon, l'intervalle de récupération est réduit de moitié après une comparaison, et cela continue jusqu'à ce que la récupération réussisse ou échoue.

Prenez l'un des 2 éléments du milieu d'un nombre pair comme élément du milieu

La récupération binaire est une méthode de récupération plus efficace, qui nécessite que le dictionnaire soit trié par clé dans la table de séquence .

Exemple de code :

#!/usr/bin/env python
import sys 
def BinarySearch(haystack, needle):
  low = 0 
  high = len(haystack) - 1 
  while(low <= high):
    mid = (low + high)/2
    midval = haystack[mid]
    if midval < needle:
      low = mid + 1 
    elif midval > needle:
      high = mid - 1 
    else:
      print mid 
      return mid 
  print -1
  return -1
if __name__ == "__main__":
  haystack = [int(i) for i in list(sys.argv[1])]
  needle = int(sys.argv[2])
  BinarySearch(haystack ,needle)

Exécuter :

python@pythontab:~$ python BinarySearch.py 123456789 4
3

Remarques :

1.'__' : Puisque les membres de la classe Python sont publics, accès public public, manque de propriétés privées comme les langages orientés objet traditionnels.

J'ai donc simplement utilisé __ pour simuler des attributs privés. Ces attributs __ sont souvent utilisés en interne et n'ont généralement pas besoin d'être remplacés. Pas besoin de lire non plus.

Le but de l'ajout de deux traits de soulignement n'est pas d'entrer en conflit avec des attributs publics communs portant le même nom, et d'autre part d'empêcher les utilisateurs de l'objet (non-développeurs) de l'utiliser à volonté.

2.__name__ == "__main__" signifie que le script du programme est exécuté directement

S'il n'est pas égal, cela signifie que le script est importé par d'autres programmes. Puis son attribut __name__. est défini sur le nom du module

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!