2.1 数值查找算法

查找是指在大量的数据中寻找到特定的元素，它是数值计算中常用的运算逻辑。

2.1.1 二分搜索算法

折半查找也称作二分查找、对数查找，是指在有序的数值序列中，从中间开始进行查找，如果查找元素小于中间元素，则在中间元素的左边区间再进行折半查找，如果查找元素大于中间元素，则在中间元素右边区间再进行折半查找，直到取得的中间值等于查找的值或查找的值不存在。

折半查找的时间复杂度：最差时间复杂度为，最优时间复杂度为，平均复杂度为；

采用递归的方式进行折半查找，最差空间复杂度为，采用迭代的方式进行折半查找，最差空间复杂度为。

总体而言，折半查找的查找性能较好，若对有序序列通过遍历的方式查找，则时间复杂度为。

2.1.2 分块查找算法

分块查找，又称作顺序查找，是一种在数据量较大的情况下，进行改进的一种查找方式，同排序方式类似。分块查找是一种介于顺序查找和二分查找的算法。由两部分组成：索引和有序的块（块中无序）。

分块查找的算法效率介于顺序查找和二分查找之间，其插入数据或者删除数据都不必移动大量的数据。它的主要缺陷在于需要一个辅助索引结构存储块的最大值和块的起始位置，以及初始化块需要的排序开销。

2.1.3 哈希查找算法

哈希查找是通过计算元素的存储地址进行的快速查找方式，它并不要求序列一定有序，可以通过如下四个步骤完成对元素进行查找。

（1）用哈希函数构造哈希表。

（2）将元素进行哈希函数过滤，选择其存储的地址。

（3）将需要查找的元素经过哈希函数映射到存储地址。

（4）在存储地址中，查找元素是否存在。

哈希函数的构造方法有很多，如直接地址法、平方取中法、除数留余法、随机数法、数字分析法及折叠法等。