数据结构之基本查找算法
public static int seqSearch(int[] arr, int key){for (int i=0; i<arr.length; i++){if (key == arr[i])return i;}return -1;}

?

?

二分查找

针对已经有序的数组,可以使用二分查找,又称折半查找

public static int binarySearch(int[] arr, int key){int low =0;int high = arr.length -1;while(low <= high){int mid = (low + high)/2;++bcount;if (key>arr[mid]) {low = mid + 1;} else if (key ==arr[mid]){return mid;} else {high = mid -1;}} return -1;}

?

?

插值查找

在折半查找中,?mid = (low + high)/2 = low + (high - low)/2,我们将右边的1/2替换为 (key-arr[low])/(arr[high]-arr[low])

当key ==arr[low]的时候 mid = low, mid往最左边移动当key== arr[high]的时候, mid=high, mid往最右边活动

可见这是一种更聪明更有倾向性的查找方法

?

public static int chazhiSearch(int[] arr, int key){int low =0;int high = arr.length -1;while(low <= high){++ccount;int mid = low + ((key-arr[low])*(high-low)/(arr[high]-arr[low]));if (key>arr[mid]) {low = mid + 1;} else if (key ==arr[mid]){return mid;} else {high = mid -1;}} return -1;}

?

测试代码

public static void main(String[] args) {int[] array = new int[]{1,2,3,4,5,6,8,9,12,15,18,20};assert(seqSearch(array, 9) == 7);assert(seqSearch(array, 8)== -1);System.out.println(binarySearch(array, 18));System.out.println(chazhiSearch(array, 18));System.out.println("bcount: " + bcount);System.out.println("ccount: " + ccount);}

?

?运行结果:

1010bcount: 3ccount: 2

?对于这种分布比较均匀的数列,插值查找的次数要比二分查找少