Python数据结构与算法-第6章-搜索算法

一案例：图书馆图书检索系统案例：图书馆图书检索系统案例描述

假设有一个大型图书馆，成千上万的书籍都有自己的标签、作者、出版日期等信息。学生、教师和研究人员经常需要查找图书馆中的书籍，以便获取相关信息或借阅书籍。

图书馆需要一个高效的图书检索系统，使用户能够根据不同的搜索条件（如书名、作者、标签等）快速地找到所需的书籍。案例：图书馆图书检索系统案例实现实现形式（具体见课本案例）可以将图书馆中的所有书籍信息构建成一个数据结构，比如使用哈希表或二叉排序树。每个书籍的信息（如书名、作者、标签等）作为键，对应的书籍对象作为值。对于图书检索系统，可以引入搜索算法来建设和优化图书检索系统，可以根据不同的搜索条件选择合适的搜索算法。包括线性搜索、二分搜索、哈希查找等。二线性搜索线性搜索基本原理线性搜索(LinearSearch)，也被称为顺序搜索(SequentialSearch)，是一种非常直观的搜索算法。它按照顺序逐个检查线性数据结构（如数组或列表）中的每个元素，直到找到所需的元素或检查完所有元素为止。线性搜索线性搜索算法

线性查找算法的Python实现如下：

需要注意的是以上实现只是以数组为背景的基本实现，基于其他线性数据结构实现的基本思路一致。线性搜索应用场景1小型数据集2数据无需排序3简单性和直观性三有序表搜索有序表搜索基本原理常见的有序表搜索算法二分查找插值查找斐波那契查找注意事项数据集合必须是有序的。不同的搜索算法适用于不同的数据集和场景。有序表搜索算法在处理大型数据集时具有较高的效率。有序表搜索二分查找算法将数组的中间位置记录的关键字与查找关键字进行比较。如果两者相等，则查找成功，返回中间位置作为结果。如果中间位置记录的关键字大于查找关键字，搜索范围缩小为前半部分，即更新搜索的上下界，排除后半部分。如果中间位置记录的关键字小于查找关键字，搜索范围缩小为后半部分，更新搜索的上下界，排除前半部分。重复步骤2至5，直到找到目标元素或者搜索范围为空，则表示目标元素不存在于数组中，查找失败。有序表搜索二分查找算法上图为“线性搜索和二分查找执行过程对比”有序表搜索插值查找算法①计算目标值估算位置mid②比较并缩小搜索范围③重复直到找到目标元素或搜索范围为空④返回结果有序表搜索插值查找算法上图为“二分查找和插值查找执行过程对比”有序表搜索斐波那契查找算法①初始化②计算划分点③比较并缩小搜索范围，将划分点位置mid与目标元素进行比较④重复步骤2到3有序表搜索斐波那契查找算法上图为“斐波那契查找过程示例”有序表搜索应用场景1数据库查询2文件系统搜索3图书馆目录4金融交易5网络搜索引擎四二叉排序树二叉排序树概念

二叉排序树（BinarySearchTree，简称BST），也称为二叉查找树或二叉搜索树。特性若其左子树不为空，则其左子树中的所有节点的值都小于该节点的值。若其右子树不为空，则其右子树中的所有节点的值都大于该节点的值。二叉排序树上图为“二叉排序树中序遍历示例”概念二叉排序树01插入02删除0304查找中序遍历二叉排序树的操作二叉排序树应用场景1数据库索引2排名系统3文件系统4编译器和解释器五哈希表与哈希搜索哈希表与哈希搜索哈希表与哈希搜索概念

哈希表（HashTable，也称散列表），是一种基于哈希函数的数据结构，用于存储键值对（Key-ValuePairs）上图为“哈希表的逻辑结构表示”哈希表与哈希搜索哈希表与哈希搜索概念

哈希搜索（HashSearch）就是一种利用哈希函数和哈希表进行快速查找的算法。哈希表与哈希搜索哈希表实现实现形式（具体见课本案例）优化形式1.哈希函数实现优化2.引入哈希冲突的解决方式哈希表与哈希搜索哈希冲突

哈希函数的作用就是希望将一个由所有key组成的较大输入空间映射到一个由数组所有索引构成的较小输出空间，因此可能会出现多个key被映射到同一个索引位置的情况，我们把这种情况称之为哈希冲突（HashCollision，也称碰撞）。上图为“哈希冲突示例”哈希表与哈希搜索哈希冲突处理哈希冲突的策略扩容优化哈希表设计哈希表与哈希搜索应用场景1URL短链接服务2缓存实现3数据库索引4分布式系统负载均衡六小结与习题小结与习题本章小结1线性搜索算法234有序表搜索算法二叉排序树哈希表小结与习题习题

？在线性搜索中，算法的时间复杂度是?A.O(1)

B.O(logn)C.O(n)

D.O(n2)

？插值查找算法适用于数据分布_________的情况?A.不均匀

B.均匀C.随机

D.不确定

？哈希搜索算法的时间复杂度通常是?A.O(1)

B.O(logn)C.O(n)

D.O(n2)小结与习题习题

？二叉排序树的中序遍历结果是?A.从左到右依次输出节点值B.从右到左依次输出节点值C.先输出根节点，再输出左子树，最后输出右子树D.先输出左子树，再输出根节点，最后输出右子树

？哈希表的冲突解决方法中，开放寻址法和链表法是其中两种常见的方法，它们的区别主要在于?A.冲突发生时的处理方式B.哈希函数的设计C.哈希表的扩容策略D冲突数据的存储方式小结与习题习题×/√有序表搜索算法的时间复杂度通常是O(logn)。×/√二叉排序树的节点删除操作需要考虑节点的子节点情况。×/√斐波那契查找算法的时间复杂度比二分查找算法更高。小结与习题习题

？二分查找算法的时间复杂度是____。

？当哈希表中的负载因子超过某个阈值时，我们可以选择对哈希表进行____，以减少哈希冲突并保持搜索效率。七实训任务实训任务任务

你作为一名软件工程师，