这篇文章是关于有序表的查找，主要包括了顺序查找的优化用法、折半查找、插值查找、斐波那契查找；
顺序优化查找：效率极为底下，但是算法简单，适用于小型数据查找；
折半查找：又称为二分查找，它是从查找表的中间开始查找。查找结果只需要找其中一半的数据记录即可。效率较顺序查找提高不少。比较适用与静态表，一次排序后不在变化；
插值查找：与折半查找比较相似，只是把中间之mid的公式进行了变换将mid = (low+high)/2;换成了mid = low + (high - low) * (key - sum[low]) / (sum[high] - sum[low]);
插值查找的效率比折半查找的效率又要高出不少，比较适用与表长较大，而关键字又分布得比较均匀的表查找；
斐波那契查找：是利用了黄金分割的原理来进行查找，平均性能要由优于折半查找，但是如果时最坏的情况，则效率低于折半查找（要查找的关键字一直比较靠近黄金分割较长的那一 段），但是运算比较简单，只有最简单的加减运算；
代码实现：
/**
* 查找
* 2016/5/1
*
**/
package cn.Link; public class Search {
public static void main(String [] args){
int n = 10; //数组长度
int key = 18; //查找关键数
int sum[] = new int[n];//有序数组 for(int i = 0;i < n;i++ ){
sum[i] = i*2;
}
System.out.println("本程序由于查找值为key的数组下标，如果返回负数，则表示没有找到，");
//打印sum数组
System.out.print("sum数组：");
for(int u: sum){
System.out.print(u+" ");
}
System.out.println("\n要查找的数为："+key); int result = Sequential_Serach(sum,n,key);
System.out.println("\n顺序优化查找结果："+result);
result = Binary_Serach(sum,n,key);
System.out.println("折半查找查找结果:"+result);
result = Interpolation_Serach(sum,n,key);
System.out.println("插值查找查找结果："+result);
result = Fibonacci_Serach(sum,n,key);
System.out.println("斐波那契查找结果："+result); } //顺序优化查找
public static int Sequential_Serach(int sum[],int n, int key){
if(key >sum[n-1] || key < sum[0])
return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到 int i;
int sum_1 = sum[0]; //记录sum首位值，用以在程序结束时还原
sum[0] = key;
i = n-1;
while(sum[i] != key){
i--;
}
sum[0] = sum_1;
if(i !=0 ){
return i;
}else{
return -1;
}
} //折半查找
public static int Binary_Serach(int sum[],int n,int key){
if(key >sum[n-1] || key < sum[0])
return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到 int low = 0;
int high = n-1;
int mid ;
while(low <= high){
mid = (low+high)/2;
if(key < sum[mid]){
high = mid -1;
}else if(key > sum[mid]){
low = mid +1;
}else{
return mid;
}
}
return -1;
} //插值查找 与折半查找只有mid的得到结果一行代码不同 优势：查找表长比较大，而关键字分布又比价均匀的查找表时平均性能比折半查找要好
public static int Interpolation_Serach(int sum[],int n,int key){ if(key >sum[n-1] || key < sum[0])
return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到
if(sum[0] == sum[n-1]) return 0; //首数和尾数相等 这是一个所有数都想等的数组 没有这一步的话会发生除零错误 int low = 1;
int high = n-1;
int mid ;
while(low <= high){
mid = low + (high - low) * (key - sum[low]) / (sum[high] - sum[low]);
if(key < sum[mid]){
high = mid -1;
}else if(key > sum[mid]){
low = mid +1;
}else{
return mid;
}
}
return -1;
} //斐波那契查找 平均性能要由优于折半查找，但是如果时最坏的情况，则效率低于折半查找如key=2
public static int Fibonacci_Serach(int sum[],int n,int key){
if(key >sum[n-1] || key < sum[0])
return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到 int low, high, mid, i, k;
low = 0;
high = n-1;
k = 0;
int F[] = new int[n];
F[0] = 0;
F[1] = F[2] = 1;
for(i = 3;i < n;i++){ //建立一个斐波那契数列，理论上这个数组是无限长的
F[i] = F[i-1] + F[i-2];
}
while(n > F[k]-1){ //计算n位于斐波那契数列的位置
k++;
} int[] sum_1 = new int[F[k]-1]; //增加数组的长度
for(i = 0;i < F[k]-1;i++){ //将不满的数值补全
if(i < n){
sum_1[i] = sum[i];
}else{
sum_1[i] = sum[n-1];
}
} while ( low <= high ){
mid = low+F[k-1]-1;
if(key < sum_1[mid]){
high = mid-1;
k = k-1;
}else if(key > sum_1[mid]){
low = mid + 1;
k = k-2;
}else{
if(mid < n ){
return mid; //找到了这个数
}else{
return n-1; //如果差找到的数在sum[n-1]以后返回sum最后一个数
}
}
}
return -1;
}
}