数据结构周边-查找

完成比完美更重要。

这是我的第二十七篇原创文章

至从上周没有更新文章之后，发现有点惰性了，可能还是冬天来的缘故吧，敲键盘有点冷。好吧，关于数据结构中的内容其实基本上已经讲解完。那我们拿两三篇文章说点数据结构的其他东西吧，例如如何利用数据结构查找，哈希表的实现的吧。这篇我们先说说查找咯。

1

查找的概念

关于查找嘛，我觉得大部分人肯定都不陌生，不就一个for的事儿，一个不行那就两个for呗。像我是做嵌入式软件的，其实程序大部分都是对数据进行处理，处理中难免要进行数据查找，我们一般用的查找都是进行循环遍历的，就是for，例如：

是吧，我们做数据查找多半都是这样吧。我们这样是因为从逻辑上来说，查找表中的数据元素之间没有本质的关系。

但是从我之前写的数据结构中的代码中可以知道，我们的查找操作实际上是可以分成静态查找和动态查找。那什么是静态查找，什么是动态查找呢？

简单的说，静态查找就是查询某个特定的数据元素是否在查找表中或者检索某个特定的数据元素的各种属性；动态查找就是在查找表中插入一个数据元素或者从查找表中删去某个数据元素。这么说就好理解了吧，我们通常用的查找都是静态的查找。

关于查找其实是一门学问，我觉嘛，只要是和计算机相关的都和查找脱不了关系，查找的效率直接影响了我们的系统工作。例如数据库的核心工作其实就是查找。他们做的工作其实很大部分都是在提高查找的效率。

循序查找的方法大伙应该都知道了，就是从第一个元素开始，一直遍历到最后一个，直到找到为止返回信息或者其他操作。这个就不写代码了。我们来说说在有序表中的二分法查找。

2

二分法查找

什么是二分法呢？顾名思义，就是一半一半的找，找到为止，但是这个的前提是我我们的查找表是有序的，我们只要取中间数据元素进行比较：（1）当给定值与中间数据元素的关键字相等时，查找成功；（2）当给定值小于中间元素时，在中间元素左区间进行二分查找；（3）当给定值大于中间元素时，在中间元素右区间进行二分查找；（4）当任意区间均无记录时，查找失败。

这个比较简单，用递归的话，几行就结束了，代码如下：

有时候，为了减小系统开销，我们会选择用非递归，采用循环的形式进行二分法，代码如下：

我们上面是我们使用的二分法的实现，但是我们想想，为什么我们非得折半，不能是折1/4的，甚至是更多呢？我记得大学那会老师说过，在不确定事件的情况下，我们都会假设他们发生与不发生的概率都是50%，所以二分法就是在这种情况之下出现的。我们用数学的方法做个二分法的进一步剖析：

如果我们想提高查找的效率，其实就是f(x) 的取值问题了。换句话说，我们得动态的查找，就是提高效率的关键。这里我们就引入了一个新的查找方式：插值查找。

3

插值查找

之前说了，插值查找的关键在于f(x)的取值，不同的f(x)的选取可以得到不同的查找算法。我们要提高他的效率，就得知道他的这个值在有序表中的动态位置，这样的话，我们查找效率就能大大的提高。这样的话，我们可以得到另一个公式：

上面的等式中，x表示我们待查找的元素相对于我们查找表中最小元素的位置。

这样的话我们的插值查找的f(x)的取值就解决了，那代码如下：

代码已经写完了，具体的是效果自己可以验证下，是不是真的减少了查找的次数。

关于插值查找，从数学的角度是可以提高效率的，但是在实际工程中，并不一定能提高效率，至少在我们的嵌入式领域，因为他的动态f(x)的数值是float，由于float在内存中特殊存储结构，计算他的效率有时候是很低的。他是减少了查找的次数，但是有时候他的执行效率比二分法查找还要低很多。

做一个查找的小结吧，我们常用的顺序查找虽然比较土，但却是其他查找算法的基础。如果我们的查找表是一个有序表，但是数据量不大的情况下我们就可以考虑二分查找了，若数据量比较大的话我们可以再考虑插值查找。如果插值查找不满意，可以考虑斐波那契查找等其他算法咯。

-END-