1.快速检索和最后回归到二分检索的快速检索
如果由于某些原因，数组长度未知，快速检索可以识别初始的搜索域。这个算法从第一个元素开始，一直加倍(*2)搜索域的上界，直到这个上界已经大于待查关键字。上界的增长如图。 之后，根据实现不同，或者采用标准的二分检索查找，或者开始另一轮的快速检索。前者可以保证O(log(n)) 的运行时间，后者则更接近O(n)的运行时间。如果我们要找的元素比较接近数组的开头，快速检索就非常有效。 总结：查找的元素在开头位置，快速检索很有效。次轮搜索使用二分法运行时间为O(log(n))，使用快速检索，运行时间接近线性。
2插值检索和最后回归到顺序查找的插值检索
在被测的算法中，插值检索可以说是“最聪明”的一个算法。它类似于人类使用电话簿的方法，它试图通过假设元素在数组中均匀分布，来猜测元素的位置。 首先它依赖搜索空间的开头和结尾线性插值中间位置，依赖中间所以的值与搜索值的大小，更新索索空间开头和结尾。算法一直重复这个步骤，直到找到元素。如果猜测是准确的，比较的次数大概是O(log(log(n))，运行时间大概是O(log(n))；但如果猜测的不对，运行时间就会是O(n)了。 插值检索的一个改进版本是，只要可推测我们猜测的元素位置是接近最终位置的(即在插值左右的某个步长范围内)，就开始执行顺序查找。相比二分检索，插值检索的每次迭代计算代价(需要计算插值)都很高，因此在最后一步采用顺序查找，无需猜测元素位置的复杂计算，很容易就可以从很小的区域（大概10个元素）中找到最终的元素位置。 围绕插值检索的一大疑问就是，O(log(log(n))的比较次数可能产生O(log(log(n))的运行时间。这并非个案，因为存储访问时间和计算下一次猜测的CPU时间相比，这两者之间要有所权衡。如果数据量很大，而且存储访问时间也很显著，比如在一个实际的硬盘上，插值检索轻松击败二分检索。然而，实验表明，如果访问时间很短，比如说RAM，插值检索可能不会产生任何好处。简而言之，插值检索依赖于存储访问时间，访问时间越短，插值检索的效果越好。
总结：插值检索比二分法计算代价高，因此存储访问时间越短使用效果越好。
3.测试代码
快速检索：
package com.search;/*快速检索*/public class Gallop implements Search{ private static long iteration; public int search(int[] arr, int val, int left, int right) { if(left>right||arr==null||arr.length==0||arr[left] > val || arr[right - 1] < val){ System.out.println("Wrong input for myGallop Searching algo"); return -1;} int jumpStep=1; int currentRight=right; while(left<=currentRight) {iteration++; if(arr[left]==val) return left; else {currentRight=left+jumpStep; if(currentRight>right) currentRight=right; if(arr[currentRight]<=val) {left=currentRight;jumpStep*=2;} else jumpStep=1;//开始下一轮快速检索，此处可以选择二分检索 } } System.out.println("未曾找到"); return -1; } public long getAccessed() { long old=iteration; iteration=0; return old; } 插值检索 package com.search;/* 插值检索*/public class Interpolation implements Search {//var为targert private static long iteration; public int search(final int[] arr, final int val, int left, int right) { if (arr == null || arr.length == 0 || arr[left] > val || arr[right - 1] < val) { return -1; } int mid; while (left<=right) { iteration++; mid = left + (right - left) * (val - arr[left]) / (arr[right] - arr[left]); //此处于二分查找不同,套用插值公式 if(arr[mid] > val)//如果val比插值小,把高位调整为插值下标的下一位 right = mid - 1; else if(arr[mid] < val) left = mid + 1; else return mid; } return -1; } public long getAccessed() {//获得循环次数 final long old =iteration; iteration = 0; return old; }} 回归顺序查找的插值检索 package com.search;/*回归顺序查找的插值检索*/public class InterpolationSequential implements Search { public long iteration; private final int distance; public InterpolationSequential(final int distance) { this.distance = distance; } public int search(final int[] arr, final int val, int left, int right) { if (arr == null || arr.length == 0 || arr[left] > val || arr[right - 1] < val) { return -1; } int mid; while (left<=right) { iteration++; float slop=((float)right - left)/(arr[right] - arr[left]); mid = (int) (left +(val - arr[left])*slop);//用插值公式 if(arr[mid] > val)//如果val比插值小,把高位调整为插值下标的下一位 right = mid - 1; else if(arr[mid] < val) left = mid + 1; else return mid; if (Math.abs(arr[mid]-val)*slop<=distance)//此处满足一定条件下回归线性查找 return sequential(arr, val, mid,arr[mid]-val ); } return -1; } private int sequential(final int[] arr, final int val, final int start, final int sign) {//顺序查找 final int step = sign < 0 ? 1: -1; for (int i = start; i < arr.length && i >= 0; i += step) { iteration++; if (arr[i]== val) return i; } return -1; } public long getAccessed() { final long old = iteration; iteration = 0; return old; }} 测试主程序：
package com.search;import java.util.Arrays;import java.util.Random; public class App { public static void main(final String[] args) { int[] arr= getArray(10000);//产生随机数组 Search b=new Binary();//二分检索法 Search s=new Gallop();//快速检索算法 Search i=new Interpolation();//插值检索算法 Search is=new InterpolationSequential(5);//回归线性查找的插值算法，设置步长为5 long start=System.nanoTime(); System.out.println("******二分检索法查找位置到的位置为 "+b.search(arr, arr[726], 0, arr.length-1)); System.out.println("循环次数 "+b.getAccessed()); System.out.println("运行时间 "+(System.nanoTime()-start)); start=System.nanoTime(); System.out.println("******快速检索法查找位置到的位置为 "+s.search(arr, arr[726], 0, arr.length-1)); System.out.println("循环次数 "+s.getAccessed()); System.out.println("运行时间 "+(System.nanoTime()-start)); start=System.nanoTime(); System.out.println("******插值法查找位置到的位置为 "+i.search(arr, arr[726], 0, arr.length-1)); System.out.println("循环次数 "+i.getAccessed()); System.out.println("运行时间 "+(System.nanoTime()-start)); start=System.nanoTime(); System.out.println("******回归线性法的插值法查找位置到的位置为 "+is.search(arr, arr[726], 0, arr.length-1)); System.out.println("循环次数 "+is.getAccessed()); System.out.println("运行时间 "+(System.nanoTime()-start)); } private static int[] getArray(final int n) {//随机数组产生 final int[] arr = new int[n]; final Random rnd = new Random(); for (int i = 0; i < arr.length; i++) { arr[i] = rnd.nextInt(n * 5);//0-5*n之间的随机整数 } Arrays.sort(arr);//排序 return arr; }} 运行结果：******二分检索法查找位置到的位置为 726循环次数 11运行时间 375237******快速检索法查找位置到的位置为 726循环次数 37运行时间 54521******插值法查找位置到的位置为 726循环次数 3运行时间 50353******回归线性法的插值法查找位置到的位置为 726循环次数 9运行时间 81141
见上,插值法效果最好。快速检索法的运行时间明显少于二分法。
4.二分检索法
Arrays.binarySearch(arr, left, right, val)；//Java二分检索法，var为查找对象元素
二分查找法：
package com.search;//2分法查找public class Binary implements Search { public long iteration;//尝试次数 public int search(final int[] arr, final int val, int left, int right) { if (arr == null || arr.length == 0 || arr[left] > val || arr[right - 1] < val) return -1; while (left <= right) { final int midpoint = (left + right) / 2; final int mid = arr[midpoint]; iteration++; if (val < mid) right = midpoint - 1; else if (mid == val) return midpoint; else left = midpoint + 1; } return -1; } public long getAccessed() { final long old = iteration; iteration = 0;//重置为0 return old; }}
本文参考：