Python实现的数据结构与算法之基本搜索详解
本文实例讲述了Python实现的数据结构与算法之基本搜索。分享给大家供大家参考。具体分析如下：
一、顺序搜索
顺序搜索 是最简单直观的搜索方法：从列表开头到末尾，逐个比较待搜索项与列表中的项，直到找到目标项（搜索成功）或者 超出搜索范围 （搜索失败）。
根据列表中的项是否按顺序排列，可以将列表分为 无序列表 和 有序列表。对于 无序列表，超出搜索范围 是指越过列表的末尾；对于 有序列表，超过搜索范围 是指进入列表中大于目标项的区域（发生在目标项小于列表末尾项时）或者指越过列表的末尾（发生在目标项大于列表末尾项时）。
1、无序列表
在无序列表中进行顺序搜索的情况如图所示：
def sequentialSearch(items, target):
for item in items:
if item == target:
return True
return False2、有序列表
在有序列表中进行顺序搜索的情况如图所示：
def orderedSequentialSearch(items, target):
for item in items:
if item == target:
return True
elif item > target:
break
return False二、二分搜索
实际上，上述orderedSequentialSearch算法并没有很好地利用有序列表的特点。
二分搜索 充分利用了有序列表的优势，该算法的思路非常巧妙：在原列表中，将目标项（target）与列表中间项（middle）进行对比，如果target等于middle，则搜索成功；如果target小于middle，则在middle的左半列表中继续搜索；如果target大于middle，则在middle的右半列表中继续搜索。
在有序列表中进行二分搜索的情况如图所示：
根据实现方式的不同，二分搜索算法可以分为迭代版本和递归版本两种：
1、迭代版本
def iterativeBinarySearch(items, target):
first = 0
last = len(items) - 1
while first <= last:
middle = (first + last) // 2
if target == items[middle]:
return True
elif target < items[middle]:
last = middle - 1
else:
first = middle + 1
return False2、递归版本
def recursiveBinarySearch(items, target):
if len(items) == 0:
return False
else:
middle = len(items) // 2
if target == items[middle]:
return True
elif target < items[middle]:
return recursiveBinarySearch(items[:middle], target)
else:
return recursiveBinarySearch(items[middle+1:], target)三、性能比较
上述搜索算法的时间复杂度如下所示：
搜索算法 时间复杂度 ----------------------------------- sequentialSearch O(n) ----------------------------------- orderedSequentialSearch O(n) ----------------------------------- iterativeBinarySearch O(log n) ----------------------------------- recursiveBinarySearch O(log n) ----------------------------------- in O(n)
可以看出，二分搜索 的性能要优于 顺序搜索。
值得注意的是，Python的成员操作符 in 的时间复杂度是O(n)，不难猜出，操作符 in 实际采用的是 顺序搜索 算法。
四、算法测试
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def test_print(algorithm, listname, target):
print(' %d is%s in %s' % (target, '' if algorithm(eval(listname), target) else ' not', listname))
if __name__ == '__main__':
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
orderedlist = sorted(testlist)
print('sequentialSearch:')
test_print(sequentialSearch, 'testlist', 3)
test_print(sequentialSearch, 'testlist', 13)
print('orderedSequentialSearch:')
test_print(orderedSequentialSearch, 'orderedlist', 3)
test_print(orderedSequentialSearch, 'orderedlist', 13)
print('iterativeBinarySearch:')
test_print(iterativeBinarySearch, 'orderedlist', 3)
test_print(iterativeBinarySearch, 'orderedlist', 13)
print('recursiveBinarySearch:')
test_print(recursiveBinarySearch, 'orderedlist', 3)
test_print(recursiveBinarySearch, 'orderedlist', 13)运行结果：
$ python testbasicsearch.py sequentialSearch: 3 is not in testlist 13 is in testlist orderedSequentialSearch: 3 is not in orderedlist 13 is in orderedlist iterativeBinarySearch: 3 is not in orderedlist 13 is in orderedlist recursiveBinarySearch: 3 is not in orderedlist 13 is in orderedlist
希望本文所述对大家的Python程序设计有所帮助。
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
AI Hentai Generator
Générez AI Hentai gratuitement.
Article chaud
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
Qui est payé plus de python ou de javascript?
Apr 04, 2025 am 12:09 AM
Il n'y a pas de salaire absolu pour les développeurs Python et JavaScript, selon les compétences et les besoins de l'industrie. 1. Python peut être davantage payé en science des données et en apprentissage automatique. 2. JavaScript a une grande demande dans le développement frontal et complet, et son salaire est également considérable. 3. Les facteurs d'influence comprennent l'expérience, la localisation géographique, la taille de l'entreprise et les compétences spécifiques.
Est-ce que distincte est lié?
Apr 03, 2025 pm 10:30 PM
Bien que distincts et distincts soient liés à la distinction, ils sont utilisés différemment: distinct (adjectif) décrit le caractère unique des choses elles-mêmes et est utilisée pour souligner les différences entre les choses; Distinct (verbe) représente le comportement ou la capacité de distinction, et est utilisé pour décrire le processus de discrimination. En programmation, distinct est souvent utilisé pour représenter l'unicité des éléments d'une collection, tels que les opérations de déduplication; Distinct se reflète dans la conception d'algorithmes ou de fonctions, tels que la distinction étrange et uniforme des nombres. Lors de l'optimisation, l'opération distincte doit sélectionner l'algorithme et la structure de données appropriés, tandis que l'opération distincte doit optimiser la distinction entre l'efficacité logique et faire attention à l'écriture de code clair et lisible.
La production de pages H5 nécessite-t-elle une maintenance continue?
Apr 05, 2025 pm 11:27 PM
La page H5 doit être maintenue en continu, en raison de facteurs tels que les vulnérabilités du code, la compatibilité des navigateurs, l'optimisation des performances, les mises à jour de sécurité et les améliorations de l'expérience utilisateur. Des méthodes de maintenance efficaces comprennent l'établissement d'un système de test complet, à l'aide d'outils de contrôle de version, de surveiller régulièrement les performances de la page, de collecter les commentaires des utilisateurs et de formuler des plans de maintenance.
Comment obtenir des données d'application et de visionneuse en temps réel sur la page de travail 58.com?
Apr 05, 2025 am 08:06 AM
Comment obtenir des données dynamiques de la page de travail 58.com tout en rampant? Lorsque vous rampez une page de travail de 58.com en utilisant des outils de chenilles, vous pouvez rencontrer cela ...
C Structure des données du langage: Le rôle clé des structures de données dans l'intelligence artificielle
Apr 04, 2025 am 10:45 AM
C Structure des données du langage: Aperçu du rôle clé de la structure des données dans l'intelligence artificielle dans le domaine de l'intelligence artificielle, les structures de données sont cruciales pour traiter de grandes quantités de données. Les structures de données fournissent un moyen efficace d'organiser et de gérer les données, d'optimiser les algorithmes et d'améliorer l'efficacité du programme. Les structures de données courantes utilisées couramment les structures de données dans le langage C comprennent: les tableaux: un ensemble d'éléments de données stockés consécutivement avec le même type. Structure: un type de données qui organise différents types de données ensemble et leur donne un nom. Liste liée: une structure de données linéaire dans laquelle les éléments de données sont connectés ensemble par des pointeurs. Stack: Structure de données qui suit le dernier principe de premier-out (LIFO). File: Structure de données qui suit le premier principe de première sortie (FIFO). Cas pratique: le tableau adjacent dans la théorie des graphiques est l'intelligence artificielle
Quelle est la raison pour laquelle PS continue de montrer le chargement?
Apr 06, 2025 pm 06:39 PM
Les problèmes de «chargement» PS sont causés par des problèmes d'accès aux ressources ou de traitement: la vitesse de lecture du disque dur est lente ou mauvaise: utilisez Crystaldiskinfo pour vérifier la santé du disque dur et remplacer le disque dur problématique. Mémoire insuffisante: améliorez la mémoire pour répondre aux besoins de PS pour les images à haute résolution et le traitement complexe de couche. Les pilotes de la carte graphique sont obsolètes ou corrompues: mettez à jour les pilotes pour optimiser la communication entre le PS et la carte graphique. Les chemins de fichier sont trop longs ou les noms de fichiers ont des caractères spéciaux: utilisez des chemins courts et évitez les caractères spéciaux. Problème du PS: réinstaller ou réparer le programme d'installation PS.
Copier et coller le code d'amour Copier et coller le code d'amour gratuitement
Apr 04, 2025 am 06:48 AM
Copier et coller le code n'est pas impossible, mais il doit être traité avec prudence. Des dépendances telles que l'environnement, les bibliothèques, les versions, etc. dans le code peuvent ne pas correspondre au projet actuel, entraînant des erreurs ou des résultats imprévisibles. Assurez-vous de vous assurer que le contexte est cohérent, y compris les chemins de fichier, les bibliothèques dépendantes et les versions Python. De plus, lors de la copie et de la collation du code pour une bibliothèque spécifique, vous devrez peut-être installer la bibliothèque et ses dépendances. Les erreurs courantes incluent les erreurs de chemin, les conflits de version et les styles de code incohérents. L'optimisation des performances doit être redessinée ou refactorisée en fonction de l'objectif d'origine et des contraintes du code. Il est crucial de comprendre et de déboguer le code copié, et de ne pas copier et coller aveuglément.
JavaScript Code Line Break: Comment gérer gracieusement l'attribut de chaîne et d'objet long?
Apr 05, 2025 am 08:03 AM
Explication détaillée des compétences de rédaction de code JavaScript Lors de l'écriture de code JavaScript, nous rencontrons souvent une ligne de code trop longue, ce qui affecte non seulement la lisibilité du code ...
