这篇文章是关于有序表的查找，主要包括了顺序查找的优化用法、折半查找、插值查找、斐波那契查找；
顺序优化查找：效率极为底下，但是算法简单，适用于小型数据查找；
折半查找：又称为二分查找，它是从查找表的中间开始查找。查找结果只需要找其中一半的数据记录即可。效率较顺序查找提高不少。比较适用与静态表，一次排序后不在变化；
插值查找：与折半查找比较相似，只是把中间之mid的公式进行了变换将mid = (low+high)/2;换成了mid = low + (high - low) * (key - sum[low]) / (sum[high] - sum[low]);
插值查找的效率比折半查找的效率又要高出不少，比较适用与表长较大，而关键字又分布得比较均匀的表查找；
斐波那契查找：是利用了黄金分割的原理来进行查找，平均性能要由优于折半查找，但是如果时最坏的情况，则效率低于折半查找（要查找的关键字一直比较靠近黄金分割较长的那一 段），但是运算比较简单，只有最简单的加减运算；
代码实现：
1 /**
2 * 查找
3 * 2016/5/1
4 *
5 **/
6 package cn.Link;
7
8 public class Search {
9 public static void main(String [] args){
10 int n = 10; //数组长度
11 int key = 18; //查找关键数
12 int sum[] = new int[n];//有序数组
13
14 for(int i = 0;i < n;i++ ){
15 sum[i] = i*2;
16 }
17 System.out.println("本程序由于查找值为key的数组下标，如果返回负数，则表示没有找到，");
18 //打印sum数组
19 System.out.print("sum数组：");
20 for(int u: sum){
21 System.out.print(u+" ");
22 }
23 System.out.println("\n要查找的数为："+key);
24
25 int result = Sequential_Serach(sum,n,key);
26 System.out.println("\n顺序优化查找结果："+result);
27 result = Binary_Serach(sum,n,key);
28 System.out.println("折半查找查找结果:"+result);
29 result = Interpolation_Serach(sum,n,key);
30 System.out.println("插值查找查找结果："+result);
31 result = Fibonacci_Serach(sum,n,key);
32 System.out.println("斐波那契查找结果："+result);
33
34 }
35
36
37
38 //顺序优化查找
39 public static int Sequential_Serach(int sum[],int n, int key){
40 if(key >sum[n-1] || key < sum[0])
41 return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到
42
43 int i;
44 int sum_1 = sum[0]; //记录sum首位值，用以在程序结束时还原
45 sum[0] = key;
46 i = n-1;
47 while(sum[i] != key){
48 i--;
49 }
50 sum[0] = sum_1;
51 if(i !=0 ){
52 return i;
53 }else{
54 return -1;
55 }
56 }
57
58 //折半查找
59 public static int Binary_Serach(int sum[],int n,int key){
60 if(key >sum[n-1] || key < sum[0])
61 return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到
62
63 int low = 0;
64 int high = n-1;
65 int mid ;
66 while(low <= high){
67 mid = (low+high)/2;
68 if(key < sum[mid]){
69 high = mid -1;
70 }else if(key > sum[mid]){
71 low = mid +1;
72 }else{
73 return mid;
74 }
75 }
76 return -1;
77 }
78
79 //插值查找 与折半查找只有mid的得到结果一行代码不同 优势：查找表长比较大，而关键字分布又比价均匀的查找表时平均性能比折半查找要好
80 public static int Interpolation_Serach(int sum[],int n,int key){
81
82 if(key >sum[n-1] || key < sum[0])
83 return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到
84 if(sum[0] == sum[n-1]) return 0; //首数和尾数相等 这是一个所有数都想等的数组 没有这一步的话会发生除零错误
85
86 int low = 1;
87 int high = n-1;
88 int mid ;
89 while(low <= high){
90 mid = low + (high - low) * (key - sum[low]) / (sum[high] - sum[low]);
91 if(key < sum[mid]){
92 high = mid -1;
93 }else if(key > sum[mid]){
94 low = mid +1;
95 }else{
96 return mid;
97 }
98 }
99 return -1;
100 }
101
102 //斐波那契查找 平均性能要由优于折半查找，但是如果时最坏的情况，则效率低于折半查找如key=2
103 public static int Fibonacci_Serach(int sum[],int n,int key){
104 if(key >sum[n-1] || key < sum[0])
105 return -1; //sum为从小到大排列，如果key大于sum[n-1]或小于sum[0]则肯定找不到
106
107 int low, high, mid, i, k;
108 low = 0;
109 high = n-1;
110 k = 0;
111 int F[] = new int[n];
112 F[0] = 0;
113 F[1] = F[2] = 1;
114 for(i = 3;i < n;i++){ //建立一个斐波那契数列，理论上这个数组是无限长的
115 F[i] = F[i-1] + F[i-2];
116 }
117 while(n > F[k]-1){ //计算n位于斐波那契数列的位置
118 k++;
119 }
120
121 int[] sum_1 = new int[F[k]-1]; //增加数组的长度
122 for(i = 0;i < F[k]-1;i++){ //将不满的数值补全
123 if(i < n){
124 sum_1[i] = sum[i];
125 }else{
126 sum_1[i] = sum[n-1];
127 }
128 }
129
130 while ( low <= high ){
131 mid = low+F[k-1]-1;
132 if(key < sum_1[mid]){
133 high = mid-1;
134 k = k-1;
135 }else if(key > sum_1[mid]){
136 low = mid + 1;
137 k = k-2;
138 }else{
139 if(mid < n ){
140 return mid; //找到了这个数
141 }else{
142 return n-1; //如果差找到的数在sum[n-1]以后返回sum最后一个数
143 }
144 }
145 }
146 return -1;
147 }
148 }
149
150