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程序设计有所帮助。
Alat AI Hot
Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik
AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.
Undress AI Tool
Gambar buka pakaian secara percuma
Clothoff.io
Penyingkiran pakaian AI
AI Hentai Generator
Menjana ai hentai secara percuma.
Artikel Panas
Alat panas
Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma
SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan
Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa
Dreamweaver CS6
Alat pembangunan web visual
SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)
Topik panas
Cara Mencantikkan Format XML
Apr 02, 2025 pm 09:57 PM
Pengindahan XML pada dasarnya meningkatkan kebolehbacaannya, termasuk lekukan yang munasabah, rehat garis dan organisasi tag. Prinsipnya adalah untuk melintasi pokok XML, tambah lekukan mengikut tahap, dan mengendalikan tag dan tag kosong yang mengandungi teks. Perpustakaan XML.Etree.ElementTree Python menyediakan fungsi Pretty_XML yang mudah yang dapat melaksanakan proses pengindahan di atas.
Cara Membuka Format XML
Apr 02, 2025 pm 09:00 PM
Gunakan kebanyakan editor teks untuk membuka fail XML; Jika anda memerlukan paparan pokok yang lebih intuitif, anda boleh menggunakan editor XML, seperti editor XML oksigen atau XMLSPY; Jika anda memproses data XML dalam program, anda perlu menggunakan bahasa pengaturcaraan (seperti Python) dan perpustakaan XML (seperti XML.Etree.ElementTree) untuk menghuraikan.
Adakah terdapat aplikasi mudah alih yang boleh menukar XML ke PDF?
Apr 02, 2025 pm 08:54 PM
Permohonan yang menukarkan XML terus ke PDF tidak dapat dijumpai kerana mereka adalah dua format yang berbeza. XML digunakan untuk menyimpan data, manakala PDF digunakan untuk memaparkan dokumen. Untuk melengkapkan transformasi, anda boleh menggunakan bahasa pengaturcaraan dan perpustakaan seperti Python dan ReportLab untuk menghuraikan data XML dan menghasilkan dokumen PDF.
Bagaimana cara menukar XML ke PDF di telefon anda?
Apr 02, 2025 pm 10:18 PM
Ia tidak mudah untuk menukar XML ke PDF secara langsung pada telefon anda, tetapi ia boleh dicapai dengan bantuan perkhidmatan awan. Adalah disyorkan untuk menggunakan aplikasi mudah alih ringan untuk memuat naik fail XML dan menerima PDF yang dihasilkan, dan menukarnya dengan API awan. API awan menggunakan perkhidmatan pengkomputeran tanpa pelayan, dan memilih platform yang betul adalah penting. Kerumitan, pengendalian kesilapan, keselamatan, dan strategi pengoptimuman perlu dipertimbangkan ketika mengendalikan penjanaan XML dan penjanaan PDF. Seluruh proses memerlukan aplikasi front-end dan API back-end untuk bekerjasama, dan ia memerlukan pemahaman tentang pelbagai teknologi.
Adakah terdapat XML percuma untuk alat PDF untuk telefon bimbit?
Apr 02, 2025 pm 09:12 PM
Tidak ada XML percuma yang mudah dan langsung ke alat PDF di mudah alih. Proses visualisasi data yang diperlukan melibatkan pemahaman dan rendering data yang kompleks, dan kebanyakan alat yang dipanggil "percuma" di pasaran mempunyai pengalaman yang buruk. Adalah disyorkan untuk menggunakan alat sampingan komputer atau menggunakan perkhidmatan awan, atau membangunkan aplikasi sendiri untuk mendapatkan kesan penukaran yang lebih dipercayai.
Adakah terdapat aplikasi mudah alih yang boleh menukar XML ke PDF?
Apr 02, 2025 pm 09:45 PM
Tiada aplikasi yang boleh menukar semua fail XML ke dalam PDF kerana struktur XML adalah fleksibel dan pelbagai. Inti XML ke PDF adalah untuk menukar struktur data ke dalam susun atur halaman, yang memerlukan parsing XML dan menjana PDF. Kaedah umum termasuk parsing XML menggunakan perpustakaan python seperti ElementTree dan menjana PDF menggunakan perpustakaan ReportLab. Untuk XML yang kompleks, mungkin perlu menggunakan struktur transformasi XSLT. Apabila mengoptimumkan prestasi, pertimbangkan untuk menggunakan multithreaded atau multiprocesses dan pilih perpustakaan yang sesuai.
Adakah kelajuan penukaran cepat apabila menukar XML ke PDF pada telefon bimbit?
Apr 02, 2025 pm 10:09 PM
Kelajuan XML mudah alih ke PDF bergantung kepada faktor -faktor berikut: kerumitan struktur XML. Kaedah Penukaran Konfigurasi Perkakasan Mudah Alih (Perpustakaan, Algoritma) Kaedah Pengoptimuman Kualiti Kod (Pilih perpustakaan yang cekap, mengoptimumkan algoritma, data cache, dan menggunakan pelbagai threading). Secara keseluruhannya, tidak ada jawapan mutlak dan ia perlu dioptimumkan mengikut keadaan tertentu.
Adakah pengubahsuaian XML memerlukan pengaturcaraan?
Apr 02, 2025 pm 06:51 PM
Mengubah kandungan XML memerlukan pengaturcaraan, kerana ia memerlukan penemuan tepat nod sasaran untuk menambah, memadam, mengubah suai dan menyemak. Bahasa pengaturcaraan mempunyai perpustakaan yang sepadan untuk memproses XML dan menyediakan API untuk melaksanakan operasi yang selamat, cekap dan terkawal seperti pangkalan data operasi.
