
Python實現(xiàn)的數(shù)據(jù)結(jié)構與算法之基本搜索詳解
本文實例講述了Python實現(xiàn)的數(shù)據(jù)結(jié)構與算法之基本搜索。分享給大家供大家參考。具體分析如下:
一、順序搜索
順序搜索 是最簡單直觀的搜索方法:從列表開頭到末尾,逐個比較待搜索項與列表中的項,直到找到目標項(搜索成功)或者 超出搜索范圍 (搜索失?。?br />
根據(jù)列表中的項是否按順序排列,可以將列表分為 無序列表 和 有序列表。對于 無序列表,超出搜索范圍 是指越過列表的末尾;對于 有序列表,超過搜索范圍 是指進入列表中大于目標項的區(qū)域(發(fā)生在目標項小于列表末尾項時)或者指越過列表的末尾(發(fā)生在目標項大于列表末尾項時)。
1、無序列表
在無序列表中進行順序搜索的情況如圖所示:
def sequentialSearch(items, target):
for item in items:
if item == target:
return True
return False
2、有序列表
在有序列表中進行順序搜索的情況如圖所示:
def orderedSequentialSearch(items, target):
for item in items:
if item == target:
return True
elif item > target:
break
return False
二、二分搜索
實際上,上述orderedSequentialSearch算法并沒有很好地利用有序列表的特點。
二分搜索 充分利用了有序列表的優(yōu)勢,該算法的思路非常巧妙:在原列表中,將目標項(target)與列表中間項(middle)進行對比,如果target等于middle,則搜索成功;如果target小于middle,則在middle的左半列表中繼續(xù)搜索;如果target大于middle,則在middle的右半列表中繼續(xù)搜索。
在有序列表中進行二分搜索的情況如圖所示:
根據(jù)實現(xiàn)方式的不同,二分搜索算法可以分為迭代版本和遞歸版本兩種:
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 False
2、遞歸版本
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)
可以看出,二分搜索 的性能要優(yōu)于 順序搜索。
值得注意的是,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)
運行結(jié)果:
$ 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程序設計有所幫助。
數(shù)據(jù)分析咨詢請掃描二維碼
若不方便掃碼,搜微信號:CDAshujufenxi
LSTM 模型輸入長度選擇技巧:提升序列建模效能的關鍵? 在循環(huán)神經(jīng)網(wǎng)絡(RNN)家族中,長短期記憶網(wǎng)絡(LSTM)憑借其解決長序列 ...
2025-07-11CDA 數(shù)據(jù)分析師報考條件詳解與準備指南? ? 在數(shù)據(jù)驅(qū)動決策的時代浪潮下,CDA 數(shù)據(jù)分析師認證愈發(fā)受到矚目,成為眾多有志投身數(shù) ...
2025-07-11數(shù)據(jù)透視表中兩列相乘合計的實用指南? 在數(shù)據(jù)分析的日常工作中,數(shù)據(jù)透視表憑借其強大的數(shù)據(jù)匯總和分析功能,成為了 Excel 用戶 ...
2025-07-11尊敬的考生: 您好! 我們誠摯通知您,CDA Level I和 Level II考試大綱將于 2025年7月25日 實施重大更新。 此次更新旨在確保認 ...
2025-07-10BI 大數(shù)據(jù)分析師:連接數(shù)據(jù)與業(yè)務的價值轉(zhuǎn)化者? ? 在大數(shù)據(jù)與商業(yè)智能(Business Intelligence,簡稱 BI)深度融合的時代,BI ...
2025-07-10SQL 在預測分析中的應用:從數(shù)據(jù)查詢到趨勢預判? ? 在數(shù)據(jù)驅(qū)動決策的時代,預測分析作為挖掘數(shù)據(jù)潛在價值的核心手段,正被廣泛 ...
2025-07-10數(shù)據(jù)查詢結(jié)束后:分析師的收尾工作與價值深化? ? 在數(shù)據(jù)分析的全流程中,“query end”(查詢結(jié)束)并非工作的終點,而是將數(shù) ...
2025-07-10CDA 數(shù)據(jù)分析師考試:從報考到取證的全攻略? 在數(shù)字經(jīng)濟蓬勃發(fā)展的今天,數(shù)據(jù)分析師已成為各行業(yè)爭搶的核心人才,而 CDA(Certi ...
2025-07-09【CDA干貨】單樣本趨勢性檢驗:捕捉數(shù)據(jù)背后的時間軌跡? 在數(shù)據(jù)分析的版圖中,單樣本趨勢性檢驗如同一位耐心的偵探,專注于從單 ...
2025-07-09year_month數(shù)據(jù)類型:時間維度的精準切片? ? 在數(shù)據(jù)的世界里,時間是最不可或缺的維度之一,而year_month數(shù)據(jù)類型就像一把精準 ...
2025-07-09CDA 備考干貨:Python 在數(shù)據(jù)分析中的核心應用與實戰(zhàn)技巧? ? 在 CDA 數(shù)據(jù)分析師認證考試中,Python 作為數(shù)據(jù)處理與分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 檢驗:數(shù)據(jù)趨勢與突變分析的有力工具? ? ? 在數(shù)據(jù)分析的廣袤領域中,準確捕捉數(shù)據(jù)的趨勢變化以及識別 ...
2025-07-08備戰(zhàn) CDA 數(shù)據(jù)分析師考試:需要多久?如何規(guī)劃? CDA(Certified Data Analyst)數(shù)據(jù)分析師認證作為國內(nèi)權威的數(shù)據(jù)分析能力認證 ...
2025-07-08LSTM 輸出不確定的成因、影響與應對策略? 長短期記憶網(wǎng)絡(LSTM)作為循環(huán)神經(jīng)網(wǎng)絡(RNN)的一種變體,憑借獨特的門控機制,在 ...
2025-07-07統(tǒng)計學方法在市場調(diào)研數(shù)據(jù)中的深度應用? 市場調(diào)研是企業(yè)洞察市場動態(tài)、了解消費者需求的重要途徑,而統(tǒng)計學方法則是市場調(diào)研數(shù) ...
2025-07-07CDA數(shù)據(jù)分析師證書考試全攻略? 在數(shù)字化浪潮席卷全球的當下,數(shù)據(jù)已成為企業(yè)決策、行業(yè)發(fā)展的核心驅(qū)動力,數(shù)據(jù)分析師也因此成為 ...
2025-07-07剖析 CDA 數(shù)據(jù)分析師考試題型:解鎖高效備考與答題策略? CDA(Certified Data Analyst)數(shù)據(jù)分析師考試作為衡量數(shù)據(jù)專業(yè)能力的 ...
2025-07-04SQL Server 字符串截取轉(zhuǎn)日期:解鎖數(shù)據(jù)處理的關鍵技能? 在數(shù)據(jù)處理與分析工作中,數(shù)據(jù)格式的規(guī)范性是保證后續(xù)分析準確性的基礎 ...
2025-07-04CDA 數(shù)據(jù)分析師視角:從數(shù)據(jù)迷霧中探尋商業(yè)真相? 在數(shù)字化浪潮席卷全球的今天,數(shù)據(jù)已成為企業(yè)決策的核心驅(qū)動力,CDA(Certifie ...
2025-07-04CDA 數(shù)據(jù)分析師:開啟數(shù)據(jù)職業(yè)發(fā)展新征程? ? 在數(shù)據(jù)成為核心生產(chǎn)要素的今天,數(shù)據(jù)分析師的職業(yè)價值愈發(fā)凸顯。CDA(Certified D ...
2025-07-03