基础查找算法分析

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 2 分钟

在之前学习了一些排序算法，得出了基础排序算法的总结。之后学习了一些查找算法，今天来对于基础的一些查找算法进行总结。

排序与查找是我们一般开发中最常用的算法。例如在开发中需要找出某个人的个人信息，就需要根据某个关键信息去查找。

顺序查找

顺序查找是按照我们思维最通俗易懂的算法，就是依次去对比，得到相等的则查找成功。当然这种算法是十分低效的，但是它对于我们需要查找的数据源，没有任何要求，就如数组中数据是可以乱序的。

二分查找

相似与之前排序算法的分治的思想，但是这种类似于分治的思想确实不同于分治。与分治得到有序结果相对应的是我们在查找的时候需要查找的数据源是有序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int halfFind(Key key) {
    int lo = 0, hi = N - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int cmp = key.compareTo(keys[mid]);
        if (cmp < 0) {
            hi = mid - 1;
        }
        else if (cmp > 0) {
            lo = mid + 1;
        } else {
            return mid;
        }
    }
    return lo;
}

上述代码是基于有序数组的二分查找算法简单实现，可以极大的减少比较次数，但是无法改变减少运行所需的时间，因为在查找源是无序的情况，将其排序成有序的情况也是需要一定运行时间的。二分查找的思想在很多查找算法里面都有体现，如插值查找、切波那锲查找、二叉查找数等都体现了这种思想。

二叉查找树

二叉查找树也是使用了二分的思想，只是在数据存储时使用二叉树的存储方式，也是链表的方式。

1
2
3
4
5
6
7
8
9
10
public Value halfTreeFind(Key key) {
	return get(root, key);
}
private Value get(Node x, Key key) {
	if (x == null) return null;
	int cmp = key.compareTo(x.key);
	if (cmp < 0) return get(x.left, key);
	else if (cmp > 0) return get(x.right, key);
	else return x.val;
}

在二叉查找树中，插入难度和查找是差不多的，运行时间主要取决于树的形状。而删除一个结点，是将其右子树中最小的结点上浮来替代。当然从其运行时间与树的形状相关，因此我们需要想办法使得树的形状基本趋于平衡，而使得效率最高。即平衡查找树。

平衡查找树

由二叉查找树的缺点而推出平衡查找树，其中包括2-3查找树、红黑树等。

在一棵完美的2-3查找树中、所有空链接到根结点的距离都是相同的。其有两种结点、具有1个数和2个数的结点、即有2个子分支和3个子分支。在查找与插入的时候都需要分别考虑，虽然情况是有限的几种，但是我还是觉得有点繁琐。

而红黑树相比较像是对于2-3树的一种升级，用红的连接来替代3结点。但是我还是比较喜欢是结点标红的意思。对于红黑树的定义在之前的文章中体现过。红黑树在于查找、插入和删除上都是十分好的，所以在java1.8的HashMap中，满足某个特定条件时会将链表转化为红黑树。

对于红黑树，所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别，当然范围查找除外。

散列表

我第一次听说散列表的时候，对于散列的意思有点迷糊，搞不懂其与哈希表的关系。后来才明白散列表就是哈希表。

哈希表中，首先需要的是一个哈希算法，最常见的就是%，除留余数法。第二点是解决冲突，一般就是拉链法与线性探测法。对于开发地址散列表中，最简单的方法就是线性探测法。

至于对于散列表，我就不详解了，HashMap源码分析看完后都能基本明白。

附

在查找算法中，普遍都是基于二分的思想进行优化的。类似于排序算法中基于分治的思想一样。虽然本文总结不够完善，但也基本理清我的思维。