搜寻

在计算机科学中，搜索算法是解决搜索问题的任何算法（即检索存储在某个数据结构中的信息，或者在问题的可行域中计算的信息。）这种结构的例子包括但不限于链表，数组或搜索树，合适的搜索算法通常取决于正在搜索的数据结构，并且还可能包括有关数据的先前知识。搜索还包含查询数据结构的算法，例如SQL SELECT命令。
搜索算法可以根据搜索机制进行分类。线性搜索算法以线性方式检查每个与目标关键字关联的记录。二分或折半搜索（二分查找算法）重复定位搜索结构的中心，并将搜索空间分成两半。比较搜索算法通过基于键的比较相继地消除记录来改进线性搜索，直到找到目标记录为止，并且可以按照定义的顺序应用于数据结构。数字搜索算法基于使用数字键的数据结构中的数字属性工作。最后，哈希根据散列函数直接将键映射到记录。在线性搜索之外进行搜索需要以某种方式对数据进行排序。此外，使用了启发式信息的方法称为启发式搜索。
搜索功能常根据其复杂性或最大理论运行时间进行评估。例如，二分查找算法的最大复杂度为



O
(
log
⁡
n
)


{\displaystyle O(\log n)}

，即对数时间复杂度，这意味着查找搜索目标所需的最大操作次数是搜索空间大小的对数函数。其它评估方式包括完备性、空间复杂性、最优性。

== 应用 ==
搜索算法的具体应用包括：

组合优化中的问题，例如：
车辆路径问题，最短路径问题的一种形式
背包问题：给定一组物品，每个物品都有一个重量和一个价值，确定每个物品在集合中的数量，使总重量小于或等于给定的极限，并且总价值尽可能大。
护士排班问题
约束满足问题，例如：
地图着色问题
填写数独或填字游戏
在博弈论中，尤其是组合博弈论中，选择下一步的最佳行动（例如极小化极大算法）
从一整套可能性中找到组合或密码
整数的因子分解（密码学中的一个重要问题）
搜索引擎优化（SEO）和网络爬虫的内容优化
通过改变工艺参数（如温度、压力和pH）来优化包括如化学反应在内的工业工艺
从数据库中检索记录
在列表或数组中查找最大值或最小值
检查给定值是否存在于一组值中

== 搜索策略 ==

=== 宽度优先搜索 ===
宽度优先搜索算法是沿着树的宽度遍历树的节点，如果发现目标，则算法中止。属于盲目搜索。

=== 深度优先搜索 ===
深度优先搜索沿着树的最大深度方向生成节点并与目标节点进行比较，只有当上次访问的节点不是目标节点，而且没有其他节点可以生成的时候，才转到上次访问节点的父节点，然后搜索该节点的其他子节点。因此深度优先搜索也称为回溯搜索。它既不是完备的，也不是最优的。有时候，某些特定的问题会产生大量重复的节点。例如“八数码”问题就是这样的，当每次运用向上…