敲黑板！经典查找算法的知识要点

      算法说明：查找是在大量的信息中寻找一个特定的信息元素的过程；在计算机应用中，查找是常用的基本运算。

      定义：根据给定的某个值，在查找表中找到一个其关键字等于给定值的数据元素（或记录）的位置；查找表是同一类型的数据元素（或记录）构成的集合。

      分类：静态查找（使用线性表结构组织数据，不改变集合内的数据元素）和动态查找（增减集合内的数据元素）；

      静态查找：顺序查找、二分查找、索引查找；

      动态查找（略）：树查找、哈希表；

      补充（查找算法的时间复杂度）：O(1)、O(n)、O(logn)；

      a) 大O记法：O()中实际是一个函数f(n)，该函数表示某个算法的耗时与数据增长量之间的关系，n表示输入数据量；

      b) O(1)：常数阶，最低的复杂度，是常量值；表示耗时与输入数据量大小无关，无论输入数据量增大多少倍，耗时都不变；

      c) O(n)：线性阶，数据量增大多少倍，耗时也增大多少倍；

      d) O(logn)：对数阶，当数据量增大n倍时，耗时增大logn倍（通常以2为底，比如当数据增大256倍时，耗时只增大8倍）；

      下面针对静态查找几种经典的查找算法做详细说明：

      1、 顺序查找

      顺序查找说明：属于无序查找算法；从数据结构线性表（数组）的一端开始，顺序扫描，依次将扫描到的数据元素与给定值k相比较，若相等则表示查找成功，返回该数据元素在线性表中的位置；否则查找失败，通常返回-1；可以通过“哨兵”进行优化；

      图例说明：原始数据：int[] a={4,6,2,8,1,9,0,3}; 要查找数字：8

      算法实现：遍历数组中所有元素，取到每个元素都与给定值进行比较；

      性能分析：

      a) 时间复杂度O(n)，性能较低；

      b) 注意：采用哨兵方式的话，如果没有找到则比较次数为 n+1；

      c) 适用于查找表中元素不多的情况

      完整代码：

      2、 二分查找

      二分查找说明：又称折半查找，属于有序查找算法；元素必须是有序的，如果是无序的则要先进行排序操作；还有两个改进的二分查找算法：插值查找和斐波那契查找，大家可以自己扩展学习；

      a) 原始数据：int[] a={10, 14, 21, 38, 45, 47, 53, 81, 87, 99}; 查找是否存在数字47；

      i.首先取中间数45跟47比较，47大于45，则取中间数右侧的数组继续进行二分查找，即{6,7,8,9}；

      ii. 反复执行上述的取中间值比较的步骤，直到找到数据或者比较完所有数据。

      b) 图例说明：

      过程说明（大家自己看看）：通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。

      如果处于middle的元素比目标值小，将左索引值移动到middle后的一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标元素大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果没有找到目标，left和right将重合。

      算法实现：用给定值k与数组中间结点mid索引位置的数据元素比较，若相等则查找成功；若不相等，再根据k与该中间结点数据元素的比较结果确定下一步查找的子表（比如：词典查单词）；折半计算mid的公式如下：

      时间复杂度：O(logn)

      a) 适用于那种一经建立就很少改动、而又经常需要查找的线性表；

      b) 不适用于链表，链表的每一个节点的地址不能在O(1)的时间复杂度内获得；

      案例1：循环方式

      案例2：递归方式

      3、 索引查找

      索引查找说明：又称为分块查找，是一种介于顺序查找和二分查找之间的一种查找方法，索引查找的基本思想是：首先查找索引表来定位块，可用二分查找或顺序查找，然后在确定的块中进行顺序查找；属于无序查找算法；将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。然后使用二分查找及顺序查找。

      算法实现：在实现索引查找算法前需要弄清楚以下三个术语：

      i. 主表：即要查找的序列。

      ii. 查找表：一般我们会将主表分成几个块，每个块中的所有元素的集合被称为是查找表。

      iii. 索引表：即索引项的集合。

      在利用索引查找时，需要先对数据进行分块；块间有序，就可以快速定位到块；

      在索引表中记录了两个数据 ：最大关键字、起始地址（指针项）；

      索引表的构建：

      i. 分块：第k 块中所有关键字< k+1块中所有关键字，（k=1, 2, …, L-1）

      ii. 建立索引项：

      关键字项：记载该块中最大关键字值；

      指针项：记载该块第一个记录在表中位置。

      iii. 所有索引项组成索引表；

      如：主表{22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53}，可以将主表分成3个子表：索引分别是（1... 6）、（7...12）、（13...18）

      块内的查找如何判断结束：

      i. 首先根据待查找关键字在索引表当中定位块。定位的方法是：只要 key>索引块i的最大关键值，则i++，定位下一个索引项；直到定位到索引块，或者把索引项都定位完也没有比key关键字大的索引项，则表示没有找到。

      示例：假设要查找关键字 38 的具体位置。首先将 38 依次和索引表中各最大关键字进行比较，因为 22 < 38 < 48，所以可以确定 38 如果存在，肯定在第二个子表中。

      ii. 如果定位到块，则在块内部进行顺序查找。

      示例：由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上，所以从该位置开始进行顺序查找，一直查找到该子表最后一个关键字（一般将查找表进行等分，具体子表个数根据实际情况而定）。结果在第 10 的位置上确定该关键字即为所找。

      性能分析：

      a) 时间复杂度：O(logn)

      b) 分块查找算法的运行效率受两部分影响：查找块的操作和块内查找的操作。

      i. 查找块的操作可以采用顺序查找，也可以采用二分查找（更优）；

      ii. 块内查找的操作采用顺序查找的方式。--思考：块内为何不能使用二分法查找？

      iii. 相比于二分查找，分块查找时间效率上更低一些；相比于顺序查找，由于在子表中进行，比较的子表个数会不同程度的减少，所以分块查找算法会更优。总体来说，分块查找算法的效率介于顺序查找和折半查找之间。

      案例：

      课后作业

      1） 生成长度为10的随机整数数组，然后参考上课时的各种方法去查找控制台输入的某个值？

      2） 有字符串数组，如：{"tom", "jerry", "jack", "rose", "scott", "allen", "clark", "king", "james", "miller"}，然后使用各种方法查找某个字符串？