数据结构与算法——查找算法

数据的查找算法较排序算法简单,并且常用的查找方案只有几种。
- 顺序查找
- 二分查找
- 插值查找
- 斐波那契查找
- 树表查找
- 分块查找
- 哈希查找
查找算法的分类
根据具体的实现逻辑不同,大体上可以把查找算法分为两大类:静态查找、动态查找,
- 静态查找:指查找表中无删除和插入操作。
- 动态查找:指查找表中有删除和插入操作。
根据查找的前提条件可以分为两大类:无序查找、有序查找
- 无序查找:指序列元素可以乱序
- 有序查找:指序列元素需要按一定的顺序排列(从小到大或从大到小)
顺序查找
通过遍历序列,与每一个序列中的元素对比,如果一致则返回
- 顺序查找属于无序查找,但仍可应用于有序序列中
- 如果序列中的元素存在重复项,在无序序列中,则需要遍历完成全部的元素后,方可返回
- 如果序列中的元素存在重复项,在有序序列中,则先遍历值大于查找值后即可返回数据。
1 | public int sequenceSearch(int value) |
二分查找
也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。
- 二分查找属于有序查找
- 如果序列中的元素存在重复项,则在找到值后,需要在该值左右两边分别查找,直到找出所有数据方可返回
- 二分查找的时间复杂度为log2n,所以如果存在1000个数,则最多需要10次才能找到数据
1 | public int binarySearch(int value) |
差值查找
差值查找是通过预估查找值到左侧/右侧节点的位置设计出的一种算法
设一个有序序列data的元素个数为n,左节点为left,右节点为right。计算每个节点元素的平均增量值为insert_value = (right-left)/(data[right]-data[left])。预估计算查找值value到左侧节点值所需的节点长度insert_length = (value-left)insert_value; 这样,就可以预估出查找值所在的位置:middle=left+insert_length。 公式汇总:left + (value-left)(right-left)/(data[right]-data[left])。
- 差值查找属于有序查找
- 如果序列中的元素存在重复项,则在找到值后,需要在该值左右两边分别查找,直到找出所有数据方可返回
- 如果序列的分布不均匀,则所需时间不一定比二分查找要好,所以常用在均匀分布的有序序列中。
1 | public int insertValueSearch(int value) |