0.搜索

搜索

• 定义：
  • 搜索算法（searching algorithm）用于在数据结构（例如数组、链表、树或图）中搜索一个或一组满足特定条件的元素

分类：

• 暴力搜索
• 自适应搜索

暴力搜索：

• 思路：遍历数据结构的每个元素
• 遍历策略：
  • 线性搜索：适用于数组和链表
  • 广度、深度优先搜索：适用于树和图
• 优缺点：
  • 优点：简单且通用性好，无须对数据做预处理和借助额外的数据结构
  • 缺点：时间复杂度为$O(n)$

自适应搜索：

• 思路：利用数据结构的特有属性等先验条件（例如有序），来优化搜索过程
• 特有属性：
  • 二分查找： 利用数据的有序性，实现高效查找，仅适用于数组。
  • 哈希查找： 利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
  • 树查找： 利用节点值的大小关系（例如二叉搜索树），基于比较节点值来快速排除节点，从而定位目标元素。
• 优缺点：
  • 优点：搜索时间复杂度低，一般为$O(logn)$，哈希表为$O(1)$
  • 缺点：需要对数据做预处理，借助额外的数据结构；维护这些数据结构也需要额外的时间和空间开销。