文章目录

一. 查找表1.定义2. 分类3. 关键字 二. 顺序查找算法三. 折半查找算法

一. 查找表

1.定义

查找表是由同一类型的数据元素构成的集合。 对于查找表的操作： 1）在查找表中查找某个具体的数据元素 2）在查找表中插入数据元素 3）从查找表中删除数据元素

2. 分类

1）静态查找表 在查找表的时候只做查找的操作，而不改动表中的数据元素，称此类查找为静态查找表。 2）动态查找表 在查找表中只做查找操作的同时进行插入数据或者删除数据的操作，称此类查找为动态查找。

3. 关键字

主关键字： 某个关键字可以唯一识别一个数据元素的时候，称这个关键字为主关键字 次关键字： 具有不唯一性的关键字

二. 顺序查找算法

从表中的最后一个元素开始，逐个和关键字作比较 如果匹配成功，那么查找成功 如果直到表中的第一个关键字查找完也没有匹配成功，那么查找失败

.

代码实现：

def sequence_search(array, key): for i in range(len(array)): if array[i] == key: return i return False array_0 = [23, 43, 12, 54, 65, 48] print(sequence_search(array_0, 12))

运行结果为：

三. 折半查找算法

折半查找算法的优缺点：

eg： 对{5,13,19,21,37,56,64,75,80,88,92} 采用折半查找算法查找关键字为21 的过程： (1) 先将开头设置为low ，56 设置为正中间的mid，92 设置为high （2）因为21 < 56， 所以区域缩小到 5~37，更新high和mid指针，low 指向5 ，mid 指向19 ， high 指向37

（3）因为 19< 21 所以在mid 和high 之间，然后更新mid 和 high指针，最后查找到21.

折半查找的性能分析： 折半查找的运行过程可以看作是用二叉树来描述，通常这棵树称为“判定树”。 代码实现：

def halffind(nums, key, low, high): """ 二分查找递归实现 """ mid = (low + high) // 2 if key == nums[mid]: return mid if low > high: return False if key > nums[mid]: return halffind(nums, key, mid + 1, high) else: return halffind(nums, key, low, mid - 1) if __name__ == "__main__": nums = [-789, -96, -53, 23, 52, 56, 520] # 测试案例 key = int(input("请输入要搜索的关键字:")) print(halffind(nums, key, 0, len(nums)))

运行结果为：