一，查找的基本概念
一是数据如何组织——查找表,
二是在查找表上如何查找——查找方法
1，查找表是由同类型的数据元素(或记录)构成的集合。
2，对查找表基本操作
●1)查询某个数据元素是否在查找表中;
●2)检索某个数据元素的各种属性;
●3)在查找表中插入一个数据元素;
●4)从查找表中删去某个数据元素。
3，查找表分类
●静态查找表
仅作查询和检索操作的查找表。
●动态查找表
"查询”结果"不在查找表中”→数据元素插入到查找表中; ;
"查询”结果为"在查找表中”的数据元素→删除。
查找过程中，往往是依据数据元素的某个数据项进行查找，这个数据项通常是数据的关键字。
关键字:是数据元素中某个数据项的值，用以标识一个数据元素。
若关键字能标识唯一的一个数据元素,
则称为主关键字。
若关键字能标识若干个数据元素,
则称为次关键字。
4，平均查找长度ASL
给定值与关键字比较次数的期望值
5，常见的查找算法：
1）顺序查找
2）二分查找
3）索引查找
4）哈希查找
二，顺序查找
顺序查找基本思想
●从表中指定位置(一般为最后一一个，第0个位置设为岗哨)的记录开始，沿某个方向将记录的关键字与给定值相比较,若某个记录的关键字和给定值相等，则查找成功;
●反之，若找完整个顺序表，都没有与给定关键字值相等的记录，则此顺序表中没有满足查找条件的记录，查找失败。
●空间复杂度: O(1)
●时间复杂度:
查找算法的基本运算是给定值与顺序表中记录关键字值的
比较。
最好情况: O(1)
最坏情况: O(n)
平均情况: O(n)
代码实现：
typedef struct{ //查找表的数据结构 ElemType *elem; //元素存储空间基址，建表时按实际长度分配，0号单元留空作为哨兵 int TableLen; //表的长度 }SSTable; int Search_Seq(SSTable ST,ElemType key) { ST.elem[0] = key; //哨兵 for(i=ST.TableLen;ST.elem[i]!=key;--i) { // 从后往前查找 return i; //若表中不存在关键字为key的元素，将查找到i为0时退出for循环。 } }
将ST.elem[0]称为"哨兵"。引入它的目的是使得Search_Seq内的循环不必判断数组是否会越界，因为满足i==0时，循环一定会跳出。引入哨兵的目的是避免很多不必要的判断语句，从而提高程序效率。
三，折半查找
1，有序表:如果顺序表中的记录按关键字值有序，即: R[i].key≤R[i+ 1].key (或R[i].key≥R[i+ 1].key)，
i=1,2...n-1，则称顺序表为有序表。
1 3 7 10 12 124
有序表
1 3 7 13 12 124
无序表
将待查关键字与有序表中间位置的记录进行比较，若相等，查找成功，若小于，则只可能在有序表的前半部分，若大于则只可能在有序表的后半部分，因此，经过一次比较，就将查找范围缩小一半,这样一直进行下去直到找到所需记录或记录不在查找表中。
2，代码实现：
int BinarySearch(DataType SL[], KeyType key, int n){ /*在长度为n的有序表SL中折半查找其关键字等于key的记录*/ /*查找成功返回其在有序表中的位置，查找失败否返回0*/ int low=1; int high=n; while(low< =high){ mid=(loW+ high)/2; if(key == SL[mid].key) {return mid;} else if( key> SL[mid].key) low=mid+ 1; else high=mid-1; } return 0; }
3，折半查找特点
折半查找的查找效率高;
平均查找性能和最坏性能相当接近;
折半查找要求查找表为有序表;
并且，折半查找只适用于顺序存储结构。
4，性能分析：
以深度为h的满二叉树为例， 即: n=2^h-1 并且查找概率相等，则
当n> 50时，可得近似结果
ASL≈log2(n+1)-1
四，索引查找
在现代社会，数据充斥着我们的生活，正因为大量的数据才能有现在如此现代化的社会，但是大量的数据也给人们带来了很大的困扰。并且有的数据是很杂乱的，会导致查找困难。
所以我们想到了一种方法，就是建立索引。
索引说白了就是一个关键字，一个能帮助你更方便查找的关键字，可以是很多东西，一个字母，一个字符串，一个数字等等。
1，索引使用方法
●先分析数据规律，建立索引
●再根据索引|进行快速定位
●在定位的地方进行细致搜索
先分块，块间有序，就可以快速定位到块。
2，索引表的构建
1) 分块:
第Rk块中所有关键字< Rk+1块中所有关键字，(k=1, 2, ..L-1）
2)建立索引项:
关键字项:记载该块中最大关键字值;
指针项:记载该块第一 个记录在表中位置。
3)所有索引项组成索引表。
3，索引表的查找
分两步，第一步是索引表的查找，第二步是查找表的查找。
索引表是有序的。
4，例子：
5，索引表的顺序查找算法思想描述
首先根据待查找关键字在索弓|表当中定位块。定位的方法是:只要key>索引块i的最大关键值，则i++, 定位下一个索引项;直到定位到索引块，或者把索弓|项都定位完也没有比key关键字大的索引项。
如果定位到块，则在块内部进行顺序查找。
6，代码实现：
int IndexSequelSearch(IndexType |s[], DataType s[], int m, KeyType key){ /*索引表为Is[0]-Is[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<Is[ i+1 ].Link)j++; if(key = = s[j].key)return j; /*查找成功*/ else return -1; /*查找失败*/ } }
typedef struct IndexType { KeyType key; int Link; } IndexType;
7，性能分析：
ASL=ASL(索引表)+ASL (块内)
五，哈希查找
