Python实现的数据结构与算法之基本搜索详解
本文实例讲述了Python实现的数据结构与算法之基本搜索。分享给大家供大家参考。具体分析如下：
一、顺序搜索
顺序搜索 是最简单直观的搜索方法：从列表开头到末尾，逐个比较待搜索项与列表中的项，直到找到目标项（搜索成功）或者 超出搜索范围 （搜索失败）。
根据列表中的项是否按顺序排列，可以将列表分为 无序列表 和 有序列表。对于 无序列表，超出搜索范围 是指越过列表的末尾；对于 有序列表，超过搜索范围 是指进入列表中大于目标项的区域（发生在目标项小于列表末尾项时）或者指越过列表的末尾（发生在目标项大于列表末尾项时）。
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算法并没有很好地利用有序列表的特点。
二分搜索 充分利用了有序列表的优势，该算法的思路非常巧妙：在原列表中，将目标项（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 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)
可以看出，二分搜索 的性能要优于 顺序搜索。
值得注意的是，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程序设计有所帮助。
相关推荐
-
Python实现的数据结构与算法之双端队列详解
本文实例讲述了Python实现的数据结构与算法之双端队列.分享给大家供大家参考.具体分析如下: 一.概述 双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构.双端队列也拥有两端:队首(front).队尾(rear),但与队列不同的是,插入操作在两端(队首和队尾)都可以进行,删除操作也一样. 二.ADT 双端队列ADT(抽象数据类型)一般提供以下接口: ① Deque() 创建双端队列 ② addFront(item) 向队首插入项 ③ addRe
-
Python实现的数据结构与算法之队列详解
本文实例讲述了Python实现的数据结构与算法之队列.分享给大家供大家参考.具体分析如下: 一.概述 队列(Queue)是一种先进先出(FIFO)的线性数据结构,插入操作在队尾(rear)进行,删除操作在队首(front)进行. 二.ADT 队列ADT(抽象数据类型)一般提供以下接口: ① Queue() 创建队列 ② enqueue(item) 向队尾插入项 ③ dequeue() 返回队首的项,并从队列中删除该项 ④ empty() 判断队列是否为空 ⑤ size() 返回队列中项的个数 队
-
python数据结构之图的实现方法
本文实例讲述了python数据结构之图的实现方法.分享给大家供大家参考.具体如下: 下面简要的介绍下: 比如有这么一张图: A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C 可以用字典和列表来构建 graph = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'], 'D': ['C'], 'E': [
-
Python数据结构与算法之图结构（Graph）实例分析
本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简
-
Python实现的数据结构与算法之链表详解
本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin
-
Python实现的数据结构与算法之快速排序详解
本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中
-
python实现dict版图遍历示例
复制代码 代码如下: #_*_coding:utf_8_import sysimport os class Graph(): def __init__(self, V, E): self.V = V self.E = E self.visited = [] self.dict = {} self.fd = open("input.txt") def initGraph(self): self.vi
-
python数据结构之图深度优先和广度优先实例详解
本文实例讲述了python数据结构之图深度优先和广度优先用法.分享给大家供大家参考.具体如下: 首先有一个概念:回溯 回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 深度优先算法: (1)访问初始顶点v并标记顶点v已访问. (2)查找顶点v的第一个邻接顶点w. (3)若顶点v的邻接顶点w存在,则继续执行:否则回
-
Python实现的数据结构与算法之基本搜索详解
本文实例讲述了Python实现的数据结构与算法之基本搜索.分享给大家供大家参考.具体分析如下: 一.顺序搜索 顺序搜索 是最简单直观的搜索方法:从列表开头到末尾,逐个比较待搜索项与列表中的项,直到找到目标项(搜索成功)或者 超出搜索范围 (搜索失败). 根据列表中的项是否按顺序排列,可以将列表分为 无序列表 和 有序列表.对于 无序列表,超出搜索范围 是指越过列表的末尾:对于 有序列表,超过搜索范围 是指进入列表中大于目标项的区域(发生在目标项小于列表末尾项时)或者指越过列表的末尾(发生在目标项
-
Python数据结构与算法之跳表详解
目录 0. 学习目标 1. 跳表的基本概念 1.1 跳表介绍 1.2 跳表的性能 1.3 跳表与普通链表的异同 2. 跳表的实现 2.1 跳表结点类 2.2 跳表的初始化 2.3 获取跳表长度 2.4 读取指定位置元素 2.5 查找指定元素 2.6 在跳表中插入新元素 2.7 删除跳表中指定元素 2.8 其它一些有用的操作 3. 跳表应用 3.1 跳表应用示例 0. 学习目标 在诸如单链表.双线链表等普通链表中,查找.插入和删除操作由于必须从头结点遍历链表才能找到相关链表,因此时间复杂度均为O(
-
Python数据结构与算法中的栈详解(3)
目录 前序.中序和后序表达式是什么? 我们为什么要学习前/后序表达式? 从中序向前序和后序转换 用Python实现从中序表达式到后序表达式的转换 计算后序表达式 总结 前序.中序和后序表达式是什么? 对于像B∗C 这样的算术表达式,可以根据其形式来正确地运算.在B∗C 的例子中,由于乘号出现在两个变量之间,因此我们知道应该用变量 B 乘以变量 C . 因为运算符出现在两个操作数的中间 ,所以这种表达式被称作中序表达式 . 来看另一个中序表达式的例子:A+B∗C.虽然运算符 “ + ” 和
-
java数据结构与算法之希尔排序详解
本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一
-
Python数据结构与算法中的栈详解(2)
目录 匹配括号 匹配符号 总结 匹配括号 接下来,我们使用栈解决实际的计算机科学问题. 比如我们都写过这样所示的算术表达式, ( 5 + 6 ) ∗ ( 7 + 8 ) / ( 4 + 3 ) (5 + 6) * (7 + 8) / (4 + 3) (5+6)∗(7+8)/(4+3),其中的括号用来改变计算顺序,或提升运算优先级. 匹配括号是指每一个左括号都有与之对应的一个右括号,并且括号对有正确的嵌套关系. 正确的嵌套关系: ( ( ) ( ) ( ) ( ) ) (()()()()) (
-
Python数据结构与算法中的栈详解
目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总
-
Python数据结构与算法中的栈详解(1)
目录 什么是栈 构建一个栈 总结 什么是栈 栈有时也被称作“下推栈”.它是有序集合,添加操作和移除操作总发生在同一端,即栈的 “顶端”,栈的另一端则被称为 “底端”.所以最新添加的元素将被最先移除,而且栈中的元素离底端越近,代表其在栈中的时间越长. 这种排序原则被称作LIFO(last-in first-out),即后进先出.它提供了一种基于在集合中的时间来排序的方式. 最近添加的元素靠近顶端,旧元素则靠近底端. 栈的例子在日常生活中比比皆是.几乎所有咖啡馆都有一个由托盘或盘子构成的栈,你可以从
-
Python数据结构与算法中的队列详解(2)
目录 传土豆 总结 传土豆 队列的一个典型方法是模拟需要以 FIFO 方式管理数据的真实场景.考虑这样一个游戏:传土豆.在这个游戏中,成员们围成一圈,并依次尽可能快地传递一个土豆.在某个时刻,大家停止传递,此时手里有土豆的成员就得退出游戏. 重复上述过程,直到只剩下一个成员. 我们将针对传土豆游戏实现通用的模拟程序.该程序接受一个名字列表和一个用于计数的常量 num ,并且返回最后剩下的那个人的名字. 我们使用队列来模拟一个环.即假设握着土豆的人位于队列的头部.在模拟传土豆的过程中,程序将这个人
-
Python数据结构与算法中的队列详解(1)
目录 什么是队列? 构建一个队列 总结 什么是队列? 队列,与栈类似,是有序集合.添加操作发生在 “尾部”,移除操作只发生在 “头部”.新元素只从尾部进入队列,然后一直向前移动到头部,直到成为下一个被移除的元素. 最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面.这种排序原则被称作FIFO(first-in first-out),即先进先出,也称先到先得.在日常生活中,我们经常排队,这便是最简单的队列例子.进电影院要排队,在超市结账要排队,买咖啡也要排队.好的队列只允许一
-
Python cookbook（数据结构与算法）找到最大或最小的N个元素实现方法示例
本文实例讲述了python找到最大或最小的N个元素实现方法.分享给大家供大家参考,具体如下: 问题:想在某个集合中找出最大或最小的N个元素 解决方案:heapq模块中的nlargest()和nsmallest()两个函数正是我们需要的. >>> import heapq >>> nums=[1,8,2,23,7,-4,18,23,42,37,2] >>> print(heapq.nlargest(3,nums)) [42, 37, 23] >&g