查找算法（静态和动态查找）

一、静态查找静态查找是指查找过程中数据集在查找过程中是不发生变化的。即数据集在查找开始前就已经完全确定并且 在查找过程中不会有插入、删除或修改操作。特点 数据集是固定的查找过程中不允许修改例如不允许插入或删除元素。 查找操作的效率通常只依赖于数据集的结构和查找算法。 常见的数据结构包括顺序表等。例子 查找一个学生在某个班级中的位置或者查找书籍在图书馆中的编号等。优点 因为数据固定不变所以可以使用一些专门为静态数据设计的高效查找算法如二分查找来加速查找过程。缺点 不适用于数据在查找过程中需要频繁更新的场景。二、动态查找动态查找是指查找过程中数据集会发生变化即数据集在查找过程中可能会有插入、删除或更新操作。因此 查找方法需要处理这些变化保证在插入、删除元素时仍能高效地进行查找。特点 数据集是动态变化的查找过程中可能会进行插入、删除或修改操作。 需要一种能够动态更新的数据结构常见的有二叉搜索树、哈希表等。 查找效率不仅取决于查找算法还与数据如何变化、如何组织和更新数据有关。例子 在线购物网站的库存管理、社交网络中的好友关系查询等。优点 能够适应频繁修改数据的场景灵活性更高。 •适合处理实时变化的数据集如数据库操作。缺点 动态更新数据结构可能会使查找效率降低需要特别优化。 •动态数据结构的实现较复杂可能需要额外的存储和计算开销。三、顺序表的查找顺序查找线性查找适用顺序表无序 / 有序都可以示例代码typedef struct { ElemType *elem; // 存储元素的数组 int length; // 顺序表的长度 } SSTable; // 顺序查找函数使用哨兵法 int Search_Seq(SSTable ST, ElemType key) { ST.elem[0] key; // 哨兵设置为目标值 int i; for (i ST.length; ST.elem[i] ! key; --i); // 从后往前查找 return i; // 返回查找结果 }二分查找折半查找⭐必考适用顺序表必须有序思想每次取中间元素比较缩小一半查找范围 示例代码int binarySearch(int a[], int n, int key) { int left 0, right n - 1; while (left right) { int mid (left right) / 2; // 中间位置 if (a[mid] key) return mid; else if (a[mid] key) left mid 1; // 去右边 else right mid - 1; // 去左边 } return -1; }四、顺序查找、二分查找、静态树表、索引表查找 区别对比表对比项顺序查找二分查找静态树表查找索引表查找索引顺序查找数据结构普通顺序表有序顺序表二叉查找树主表 索引表分块是否要求有序无序 / 有序均可必须整体有序有序 已知概率块内无序块间有序核心思想逐个遍历比较折半缩小范围按概率建树最小 ASL先查索引确定块再在块内顺序查查找过程从头到尾找折半比较按树路径查找查索引→定位块→块内顺序查找时间复杂度O(n)O(log₂n)O (log₂n)最优O (√n)分块最优空间复杂度O(1)O(1)O(n)~O(n²)O (n)存索引插入删除简单复杂要保持有序静态不支持动态方便只影响对应块适用场景数据量小、无序有序静态数据、高频查找静态 概率不均、追求最优 ASL数据量大、动态变化多、兼顾效率一句话区分顺序查找最简单但最慢二分查找有序最快但增删麻烦静态树表已知概率下理论最优但不能动态改索引表分块查找兼顾查找效率 插入删除工程最实用