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衣類リムーバー
Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。
人気の記事
ホットツール
メモ帳++7.3.1
使いやすく無料のコードエディター
SublimeText3 中国語版
中国語版、とても使いやすい
ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
ドリームウィーバー CS6
ビジュアル Web 開発ツール
SublimeText3 Mac版
神レベルのコード編集ソフト（SublimeText3）
ホットトピック
1677
14
1430
52
1333
25
1278
29
1257
24
PHPおよびPython：さまざまなパラダイムが説明されています
Apr 18, 2025 am 12:26 AM
PHPは主に手順プログラミングですが、オブジェクト指向プログラミング（OOP）もサポートしています。 Pythonは、OOP、機能、手続き上のプログラミングなど、さまざまなパラダイムをサポートしています。 PHPはWeb開発に適しており、Pythonはデータ分析や機械学習などのさまざまなアプリケーションに適しています。
PHPとPythonの選択：ガイド
Apr 18, 2025 am 12:24 AM
PHPはWeb開発と迅速なプロトタイピングに適しており、Pythonはデータサイエンスと機械学習に適しています。 1.PHPは、単純な構文と迅速な開発に適した動的なWeb開発に使用されます。 2。Pythonには簡潔な構文があり、複数のフィールドに適しており、強力なライブラリエコシステムがあります。
Sublime Code Pythonを実行する方法
Apr 16, 2025 am 08:48 AM
PythonコードをSublimeテキストで実行するには、最初にPythonプラグインをインストールし、次に.pyファイルを作成してコードを書き込み、Ctrl Bを押してコードを実行する必要があります。コードを実行すると、出力がコンソールに表示されます。
PHPとPython：彼らの歴史を深く掘り下げます
Apr 18, 2025 am 12:25 AM
PHPは1994年に発信され、Rasmuslerdorfによって開発されました。もともとはウェブサイトの訪問者を追跡するために使用され、サーバー側のスクリプト言語に徐々に進化し、Web開発で広く使用されていました。 Pythonは、1980年代後半にGuidovan Rossumによって開発され、1991年に最初にリリースされました。コードの読みやすさとシンプルさを強調し、科学的コンピューティング、データ分析、その他の分野に適しています。
Python vs. JavaScript：学習曲線と使いやすさ
Apr 16, 2025 am 12:12 AM
Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。
Golang vs. Python：パフォーマンスとスケーラビリティ
Apr 19, 2025 am 12:18 AM
Golangは、パフォーマンスとスケーラビリティの点でPythonよりも優れています。 1）Golangのコンピレーションタイプの特性と効率的な並行性モデルにより、高い並行性シナリオでうまく機能します。 2）Pythonは解釈された言語として、ゆっくりと実行されますが、Cythonなどのツールを介してパフォーマンスを最適化できます。
vscodeでコードを書く場所
Apr 15, 2025 pm 09:54 PM
Visual Studioコード（VSCODE）でコードを作成するのはシンプルで使いやすいです。 VSCODEをインストールし、プロジェクトの作成、言語の選択、ファイルの作成、コードの書き込み、保存して実行します。 VSCODEの利点には、クロスプラットフォーム、フリーおよびオープンソース、強力な機能、リッチエクステンション、軽量で高速が含まれます。
メモ帳でPythonを実行する方法
Apr 16, 2025 pm 07:33 PM
メモ帳でPythonコードを実行するには、Python実行可能ファイルとNPPEXECプラグインをインストールする必要があります。 Pythonをインストールしてパスを追加した後、nppexecプラグインでコマンド「python」とパラメーター "{current_directory} {file_name}"を構成して、メモ帳のショートカットキー「F6」を介してPythonコードを実行します。
