搜索算法

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