查找表
同一类型的数据元素（或记录）的集合。
关键字
数据元素（或记录）中某个数据项的值，用它可以标识（识别）一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary key）。用以识别若干记录的关键字，是次关键字（Secondary Key）。
查找
查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
若查找到了数据元素，则查找成功；否则，查找失败。
查找分类：
1、静态查找和动态查找
静态查找：特定元素是否存在；查找特定元素的属性。
动态查找：插入数据元素；删除数据元素。
2、有序查找和无序查找
静态查找表各种表示方法：以顺序表或线性链表表示静态查找表
顺序表的顺序查找例子：
private static int arrays [] = {12,15,3,56,234,13,76,45,23};
public static void main(String[] args) {
System.out.println(findInt(45));
}
private static int findInt(int key){
for(int i = 1; i <= arrays.length ; i++){
if(arrays[i] == key){
return arrays[i] ;
}
}
return 0;
}
那么简单的数据查找可以这样做，如果是非常庞大的数据需要查找某个关键字的话，又怎么做呢？有没有一个标准去衡量查找的优劣呢？
我们需要知道如下几个定义：
1、查找操作的性能分析：时间复杂度、空间复杂度、算法的其他性能。
2、衡量查找算法好坏的依据：其关键字和给定值进行过比较的记录个数的平均值”
3、平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。
有序表的查找
折半查找、斐波那契查找、插值查找。
折半查找
//折半查找算法
public static int Binary_Search(int arr[], int n, int key) {
int mid;
int low = 1;//最低元素索引
int high = n;//最高元素索引
int flag = 0;//哨兵用来记录查找次数
while (low <= high) {
mid = (low + high) / 2;
if (key < arr[mid]) {
high = mid - 1;
flag++;
} else if (key > arr[mid]) {
low = mid + 1;
flag++;
} else
return mid;
}
return 0;
}
折半查找性能分析
折半查找查找过程也可用二叉树描述
折半查找的效率比顺序查找高，但折半查找只能适用于有序表，且限于顺序存储结构（对线性链表无法进行折半查找）。
插值查找：在折半查找的基础上改进。
在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。那么就不一定是折半了，有可能折一小部分，有可能折更多。
public static int chazhiSearch(int arr[], int n, int key) {
int low, high, mid;
low = 1;//最低元素索引
high = n;//最高元素索引
while (low <= high) {
//关键算法，效率提高不少
mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
if (key < arr[mid]) {
high = mid - 1;
} else if (key > arr[mid]) {
low = mid + 1;
} else {
return mid;
}
}
return 0;
}
可见，关键字分布比较均匀的情况下，比折半查找更快，
斐波那契查找：
斐波那契查找的平均性能比折半查找的好，但最坏的情况比它差。还有一个优点，分割时，只需进行加、减运算。
public static int fibonacciSearch(int arr[], int n, int key) {
//构造一个斐波拉切数列
int F[] = new int[20];
F[0] = 0;
F[1] = 1;
for (int j = 2; j < F.length; j++) {
F[j] = F[j - 1] + F[j - 2];//递归构造斐波拉契数列
}
int mid;
int i;
int low = 1;
int high = n;
int k = 0;
while (n > F[k] - 1) {
k++;
}
for (i = n; i < F[k] - 1; i++) {
arr[i] = arr[n];//必须扩展对象数组的后面几位元素，否则容易越界
}
while (low <= high) {
mid = low + F[k - 1] - 1;
if (key < arr[mid]) {
high = mid - 1;
k = k - 1;
} else if (key > arr[mid]) {
low = mid + 1;
k = k - 2;
} else {
if (mid <= n) {
return mid;
} else {
return n;
}
}
}
return 0;
}
访问频度域？
以上的查找都是等概率的查找，那不同概率的查找是怎么样的呢？ 这就要用到 静态树表的查找
带权路径长度和最短的为静态最优查找树。
索引顺序表的查找（分块查找）
哈希查找?
