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程序设计有所帮助。
ホットAIツール
Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ
AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。
Undress AI Tool
脱衣画像を無料で
Clothoff.io
AI衣類リムーバー
AI Hentai Generator
AIヘンタイを無料で生成します。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
携帯電話でXMLをPDFに変換するとき、変換速度は高速ですか？
Apr 02, 2025 pm 10:09 PM
Mobile XMLからPDFへの速度は、次の要因に依存します。XML構造の複雑さです。モバイルハードウェア構成変換方法（ライブラリ、アルゴリズム）コードの品質最適化方法（効率的なライブラリ、アルゴリズムの最適化、キャッシュデータ、およびマルチスレッドの利用）。全体として、絶対的な答えはなく、特定の状況に従って最適化する必要があります。
携帯電話のXMLファイルをPDFに変換する方法は？
Apr 02, 2025 pm 10:12 PM
単一のアプリケーションで携帯電話でXMLからPDF変換を直接完了することは不可能です。クラウドサービスを使用する必要があります。クラウドサービスは、2つのステップで達成できます。1。XMLをクラウド内のPDFに変換し、2。携帯電話の変換されたPDFファイルにアクセスまたはダウンロードします。
C言語合計の機能は何ですか？
Apr 03, 2025 pm 02:21 PM
C言語に組み込みの合計機能はないため、自分で書く必要があります。合計は、配列を通過して要素を蓄積することで達成できます。ループバージョン：合計は、ループとアレイの長さを使用して計算されます。ポインターバージョン：ポインターを使用してアレイ要素を指し示し、効率的な合計が自己概要ポインターを通じて達成されます。アレイバージョンを動的に割り当てます：[アレイ]を動的に割り当ててメモリを自分で管理し、メモリの漏れを防ぐために割り当てられたメモリが解放されます。
XMLをPDFに変換できるモバイルアプリはありますか？
Apr 02, 2025 pm 09:45 PM
XML構造が柔軟で多様であるため、すべてのXMLファイルをPDFSに変換できるアプリはありません。 XMLのPDFへのコアは、データ構造をページレイアウトに変換することです。これには、XMLの解析とPDFの生成が必要です。一般的な方法には、ElementTreeなどのPythonライブラリを使用してXMLを解析し、ReportLabライブラリを使用してPDFを生成することが含まれます。複雑なXMLの場合、XSLT変換構造を使用する必要がある場合があります。パフォーマンスを最適化するときは、マルチスレッドまたはマルチプロセスの使用を検討し、適切なライブラリを選択します。
推奨されるXMLフォーマットツール
Apr 02, 2025 pm 09:03 PM
XMLフォーマットツールは、読みやすさと理解を向上させるために、ルールに従ってコードを入力できます。ツールを選択するときは、カスタマイズ機能、特別な状況の処理、パフォーマンス、使いやすさに注意してください。一般的に使用されるツールタイプには、オンラインツール、IDEプラグイン、コマンドラインツールが含まれます。
XMLを写真に変換する方法
Apr 03, 2025 am 07:39 AM
XMLは、XSLTコンバーターまたは画像ライブラリを使用して画像に変換できます。 XSLTコンバーター：XSLTプロセッサとスタイルシートを使用して、XMLを画像に変換します。画像ライブラリ：PILやImageMagickなどのライブラリを使用して、形状やテキストの描画などのXMLデータから画像を作成します。
携帯電話でXMLを高品質でPDFに変換するにはどうすればよいですか？
Apr 02, 2025 pm 09:48 PM
携帯電話の高品質でXMLをPDFに変換する必要があります。クラウドでXMLを解析し、サーバーレスコンピューティングプラットフォームを使用してPDFを生成します。効率的なXMLパーサーとPDF生成ライブラリを選択します。エラーを正しく処理します。携帯電話の重いタスクを避けるために、クラウドコンピューティングの能力を最大限に活用してください。複雑なXML構造の処理、マルチページPDFの生成、画像の追加など、要件に応じて複雑さを調整します。デバッグを支援するログ情報を印刷します。パフォーマンスを最適化し、効率的なパーサーとPDFライブラリを選択し、非同期プログラミングまたは前処理XMLデータを使用する場合があります。優れたコードの品質と保守性を確保します。
XML形式を開く方法
Apr 02, 2025 pm 09:00 PM
ほとんどのテキストエディターを使用して、XMLファイルを開きます。より直感的なツリーディスプレイが必要な場合は、酸素XMLエディターやXMLSPYなどのXMLエディターを使用できます。プログラムでXMLデータを処理する場合、プログラミング言語（Pythonなど）やXMLライブラリ（XML.ETREE.ELEMENTTREEなど）を使用して解析する必要があります。
