有序表查找
/* 主函数 */public class OrderTableSearch {public static void main(String[] args) {int [] a= {0,1,16,24,35,47,59,62,73,88,99}; System.out.println(FibonacciSearch(a, 10, 88));System.out.println(InsertKeySearch(a, 10, 88));System.out.println(BinarySearch(a, 10, 88));}一、折半查找
/* 折半查找 *//* 输出：9 */static int BinarySearch(int [] a, int n, int key){int low, high, mid;low = 0;high = n;while(low <= high){mid = (low + high) / 2; /* 折半 */if (key < a[mid]){high = mid - 1;}else if (key > a[mid]){low = mid + 1;}else return mid;}return 0;}二、插值查找
/* 插值排序 *//* 输出：9 */static int InsertKeySearch(int [] a, int n, int key){int low, high, mid;low = 0;high = n;while(low <= high){/* 插值查找的计算公式 */mid = low + (high - low)*(key - a[low])/(a[high] - a[low]);if (key < a[mid]){high = mid - 1;}else if (key > a[mid]){low = mid + 1;}else return mid;}return 0;}三、斐波那契查找
/* 斐波那契排序 *//* 输出：9 */static int FibonacciSearch(int [] a, int n, int key){int [] F = {0,1,1,2,3,5,8,13,21,34};int low, high, mid, i, k;low = 1;high = n;k = 0;while (n > F[k]-1) /* 计算n位于斐波那契数列的位置 */k++;while (low <= high) {mid = low + F[k-1] -1;if (key < a[mid]){high = mid - 1;k = k - 1;}else if (key > a[mid]){low = mid + 1;k = k - 2;}else {if (mid <= n)return mid;elsereturn n;}}return 0;}
四、三种查找方法的比较
平均性能：斐波那契>折半>插值，因为折半查找是加法与除法的运算，插值为四则运算，斐波那契加减运算。