三.顺序查找
顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。
1. 元素查找介绍
查找也被称为检索，算法的主要目的是在某种数据结构中找出满足给定条件的元素（以等值匹配为例）。如果找到满足条件的元素则代表查找成功，否则查找失败。
在进行查找时，对于不同的数据结构以及元素集合状态，会有相对匹配的算法，在使用时也需要注意算法的前置条件。在元素查找相关文章中只讨论数据元素只有一个数据项的情况，即关键字（key）就是对应数据元素的值，对应到具体的数据结构，可以理解为一维数组。
顺序查找
也称线性查找，是最简单的查找方法。思路也很简单，从数组的一边开始，逐个进行元素的比较，如果与给定的待查找元素相同，则查找成功；如果整个扫描结束后，仍未找到相匹配的元素，则查找失败。
顺序查找的实现
作为一种最直观的查找方法， 其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。
typedef struct //查找表的数据结构 { ElemType *elem; //动态数组基址，建表时按实际长度分配，0号单元留空 Int TableLen; //表的长度 }SSTable; //顺序查找 int Search_Seq(SSTable ST, ElemType key) { //在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元素在表中的位置 for(i=ST.TableLen; ST.elem[i]!=key; --i); //从后往前找 return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环 }
顺序查找的实现（哨兵）
下面给出其算法，主要是为了说明其中引入的"哨兵"的作用。
typedef struct //查找表的数据结构（顺序表） { ElemType *elem; //动态数组基址，建表时按实际长度分配，0号单元留空 Int TableLen; //表的长度 }SSTable; //顺序查找 int Search_Seq(SSTable ST, ElemType key) { //在顺序表ST中顺序查找关键字为key的元素。若找到则返回该元素在表中的位置 ST.elem[0]=key; //哨兵 int i; for(i=ST.TableLen; ST.elem[i]!=key; --i); //从后往前找 return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环 }
上述算法中，将ST.elem[0]称为"哨兵"。引入它的目的是使得Search_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。需要说明的是，在程序中引入"哨兵"并不是这个算法独有的。引入"哨兵"可以避免很多不必要的判断语句，从而提高程序效果。
查找效率分析
对于有n个元素的表，给定值key与表中第i个元素的关键字相等，即定位第i个元素时，需进行n-i+1次关键字的比较，即Ci=n-i+1。查找成功时，顺序查找的平均长度为
ASL成功=∑Pi(n-i+1)
当每个元素的查找概率相等， 即Pi= 1/n时，有
ASL成功=∑Pi(n-i+1)=(n+1)/2
查找不成功时，与表中各关键字的比较次数显然是n + 1次，从而顺序查找不成功的平均查找长度为ASL不成功=n+ 1。
通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列。
综上所述，顺序查找的缺点是当n较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键码有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。
只做简单概念简读理解；具体可查看 博客
折半查找
折半查找(Binary Searh) 也称二分查找，它是一种效率较高的查找方法。使用该算法的前提要求是元素已经有序，因为算法的核心思想是尽快的缩小搜索区间，这就需要保证在缩小范围的同时，不能有元素的遗漏， 而且表中元素也按关键字有序排列。在下面及后续的讨论中，均假设有序表是递增有序的。
折半查找的查找过程为：从表的中间记录开始， 如果给定值和 中间记录的关键字相等， 则查找成功；如果给定值大于或者小千中间记录的关键字，则在表中大于或小千中间记录的那一半中查找，这样重复操作， 直到查找成功或者在某一步中查找区间为空， 则代表查找失败。
折半查找每一次查找比较都使查找范围缩小一半，与顺序查找相 比，很显然会提高查找效率。
为了标记查找过程中每一次的查找区间，下面分别用low和high来表示当前查找区间的下界和上界，mid为区间的中间位置。
【算法步骤】
1 ：置查找区间初值，low 为 1,high为表长。
2 ：当 low 小于等于 high 时， 循环执行以下操作：
• mid取值为 low 和 high 的中间值；
• 将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置 mid ;
• 若不相等则利用中间位置记录将表对分成前、后两个子表 。如果 key 比中间位置记录
的关键字小，则 high 取为 mid - 1 , 否则 low 取为 mid + l 。
3 ：循环结束，说明查找区间为空，则查找失败，返回 0。
【算法描述】
int Search_Bin(SSTable ST, KeyType key) { //在有序表ST中折半查找其关键字等于key的数据元素。若找到， 则函数值为该元素在表中的位置， 否则为0 low = l; high = ST.length; //置查找区间初值 while (low <= high) { mid = (low + high) / 2; if (key == ST.R[mid].key) return mid; //找到待查元素 else if (key < ST.R[mid].key) high = mid - 1; //继续在前一子表进行查找 else low = mid + l; //继续在后一子表进行查找 return 0; }
唯一需要注意的是，循环执行的条件是 low <= high , 而不是low < high，因为 low = high 时，查找区间还有最后一个结点，还要进一步比较 。
索引查找
索引查找主要分为基本索引查找和分块查找，核心思想是对于无序的数据集合，先建立索引表，使得索引表有序或分块有序，结合顺序查找与索引查找的方法完成查找。
数据太多，杂乱无章，查找困难！但是，在数据库中利用索引能过很容易的就查找到我们所需要的数据。
索引查找又称为分块查找，是一种介于顺序查找和二分查找（折半查找）之间的一种查找方法，索引查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。
在实现索引查找算法前需要弄清楚以下三个术语。
（1）主表：即要查找的序列。
（2）查找表：一般我们会将主表分成几个块，每个块中的元素被称为是查找表。
（3）索引表：即索引项的集合。
在利用索引查找时，需要先对数据进行分块。
在索引表中记录了两个数据 ：
最大关键字，起始地址（指针项）。
索引表的构建：
分块：
第Rk 块中所有关键字< Rk+1块中所有关键字（k=1, 2, …, L-1）
建立索引项：
关键字项：记载该块中最大关键字值；
指针项： 记载该块第一个记录在表中位置。
所有索引项组成索引表。
如下数据索引查找：
上数据转化成索引表如下：
当我要查找数据：
k = 38 时
是大于第一个块中的最大关键字，但是小于第二个块中的最大关键字，易得 和数据进行匹配的数据在第二个块中，在第二个块中进行顺序查找。查找出结果，返回索引。
k = 50 时
是大于第二个块中的最大关键字，但是小于第三个块中的最大关键字，易得 和数据进行匹配的数据在第三个块中，在第三个块中进行顺序查找。查找出结果，返回索引。
但是问题就来了 ······························
块内的查找如何判断结束 ？
首先根据待查找关键字在索引表当中定位块。定位的方法是：只要 key>索引块i的最大关键值，则i++，定位下一个索引项；直到定位到 索引块，或者把索引项都定位完也没有比key关键字大的索引项。 如果定位到块，则在块内部进行顺序查找。
int IndexSequelSearch(IndexType ls[], DataType s[], int m, KeyType key){ /*索引表为ls[0]-ls[m-1]，顺序表为s */ i=0; while(i<m && key>ls [i ].key) i++; /*块间查找*/ if(i==m)return -1; /*查找失败*/ else{ /*在块内顺序查找*/ j=ls[ i ].Link; while(Key!=s[j].key && j<ls[ i+1 ].Link) j++; if(key = = s[j].key) return j; /*查找成功*/ else return -1; /*查找失败*/ } }
索引顺序查找的ASL？
• ASL=ASL(索引表）+ASL（块内）。
总结：
在索引查找方法中 ，利用的是首先将所得的数据进行排序分块，
将要查找的数据 k 和分块中的最大值进行比较，判断k在哪个分块，
在分块中判断是否数据中有和K 匹配的数据。
返回结果：
注意：
查找表中的数据可以利用顺序存储结构或者是链式存储结构。（建议采用链式存储结构）。
输入
n个数的序列，通常直接存放在数组中，可以是任何顺序。
待查找元素key。
输出
查找成功：返回元素所在位置的编号。
查找失败：返回-1或自定义失败标识。
算法说明
算法执行的过程简单粗暴，就是从数组的一端开始逐个扫描，挨个元素进行比较，直到找到元素位置，或将所有的元素扫描一遍。
