Java有序表查找：折半查找、二分查找、差值查找和斐波那契查找
【尊重原创，转载请注明出处】/guyuealian/article/details/51106238 目前查找方法主要：顺序查找、有序查找（分为：折半查找即二分查找、差值查找和斐波那契查找方法）、线性索引查找、二叉排序树、平衡二叉树（AVL树）以及多路查找树（B树）、散列表查找（哈希表）等查找方法【1】顺序查找：是最简单的查找方法，其时间复杂度为O(n)，是通过构造一个线性表，采用遍历的方法，将记录与关键字一个一个的对比，若相等则查找成功，若全都不相等，则查找失败即记录不存在；【2】有序查找：顺序表的记录一般是无序，而有序表的记录是有序的；使用有序表查找方法时，前提条件是待查找的记录必须是已经排好序的。有序查找分为：折半查找即二分查找、差值查找和斐波那契查找方法（1）折半查找法：又称二分查找，是最经典的有序表查找，它的前提是线性表中的记录必须是有序的（通常从小到大排列），线性表采用顺序存储的方式；其基本思路是：将关键字key与中间记录（（low+high）/2）进行比较；若相等，则查找成功；若关键字小于中间记录，则说明关键字可能在下半区；若大于，则说明关键字可能在上半区；不断重复上述过程，直到查找成功或失败； Java代码如下：
package javatest1;public class JavaTest1 {public static void main(String[] args) {int[] num = { 1, 2, 3, 4, 5, 6 };//必须有序int index = Binary_Search(num, 5);System.out.print(index);}/* num：有序表（由小到大排列）* key：要查找的关键字* return：还回查找到关键字的下标，没有找到则还回-1*/private static int Binary_Search(int[] num, int key) {int low, high, mid;low = 0;high = num.length - 1;while (low <= high) {mid = (low + high) / 2;if (key < num[mid])high = mid - 1;else if (key > num[mid])low = mid + 1;else// 如果等于则直接还回下标值return mid;}return -1;}}
（2）插值查找：对二分法查找进行改进，将要查找的关键字key与查找表中的最大最小值记录进行比较后，再确定查找的范围。在二分法查找中，是以中间记录作为查找分区的，即将表一分为二，分为上下两个查找分区：而插值查找采用插值公式的方法，来确定查找分区。可简单这样理解，比如有100个数其值在0~1000范围之间从小到大排序，你要查找关键字为5的位置下标，若采用二分法，则大概在500的地方往下查找，但采用插值的方法，可以通过插值计算出5这个关键字应该在靠近0的地方，因此查找时从50往下开始查找，从而提高效率：
因此插值查找只需要在折半查找算法的代码中简单修改一下即可：
package javatest1;public class JavaTest1 {public static void main(String[] args) {int[] num = { 1, 2, 3, 4, 5, 6 };// 必须有序int index = Insert_Search(num, 5);System.out.print(index);}/** num：有序表（由小到大排列） key：要查找的关键字 return：还回查找到关键字的下标，没有找到则还回-1*/private static int Insert_Search(int[] num, int key) {int low, high, mid;low = 0;high = num.length - 1;while (low <= high) {// mid = (low + high) / 2;//二分查找mid = low + (high - low) * (key - num[low])/ (num[high] - num[low]); // 插值查找if (key < num[mid])high = mid - 1;else if (key > num[mid])low = mid + 1;else// 如果等于则直接还回下标值return mid;}return -1;}}
