折半和插值查找 --------java实现

一、递归写法，返回待查数据下标

原理很简单，网上很多解释，这里就不叙述了

/** * 二分查找 * @author * @date 2019/10/3112:54 */ public class BinarySearch { public static void main(String[] args) { //必须是有序的 int arr[]={2,5,7,8,10,22,22}; int i = binarySearch(arr, 0, arr.length - 1, 8); System.out.println(i); } public static int binarySearch(int[]arr, int left, int right, int value){ //当left>right时，说明完成整个数组的递归，仍然没有找到，结束递归 if (left>=right){ return -1; } int mid=(left+right)/2; int midVal=arr[mid]; if (value>midVal){//向右递归 return binarySearch(arr,mid+1,right,value); }else if (value<midVal){ return binarySearch(arr,left,mid-1,value); }else { return mid; } }

二、返回满足条件的多个下标

第一种方法当碰到目标值时就会立刻返回，但如果有多个值相同，则无法全部返回

当找到目标值是不立刻返回，循环向其左右扫描，查找相同值的数据，存到List集合后返回

public static void main(String[] args) { //必须是有序的 int arr[]={2,5,7,8,10,22,22}; List<Integer> list = binarySearch(arr, 0, arr.length, 22); System.out.println(list); } public static List<Integer> binarySearch(int[]arr, int left, int right, int value){ //当left>right时，说明完成整个数组的递归，仍然没有找到，结束递归 if (left>=right){ return new ArrayList<Integer>(); } int mid=(left+right)/2; int midVal=arr[mid]; if (value>midVal){//向右递归 return binarySearch(arr,mid+1,right,value); }else if (value<midVal){ return binarySearch(arr,left,mid-1,value); }else { //找到mid值，向mid左边扫描，将所有满足满足value的元素下标加到集合中 List<Integer>list=new ArrayList<Integer>(); int temp = mid -1; while (true){ if (temp<0 || arr[temp] !=value){ break; } //放入集合 list.add(temp); temp-=1; } list.add(mid); //同样道理向右扫描 temp = mid +1; while (true){ if (temp>arr.length-1 || arr[temp] !=value){ break; } //放入集合 list.add(temp); temp+=1; } return list; } }

结果：[5, 6]

三、插值查找

二分查找问题： 当查找的数是边界值时，需要递归数次才可以查到

插值原理： 1.插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找 2.修改二分查找求mid的公式

int mid = left + (right – left) * (targetValue– arr[left]) / (arr[right] – arr[left])

代码实现：

/** * 插值查找 * @author * @date 2019/10/3112:54 */ public class insertValueSearch { public static int insertValueSearch(int[]arr, int left, int right, int value){ int count=0; System.out.println(count++); if (left>right || value<arr[0] ||value>arr[arr.length-1]){ return -1; } int mid=left + (right -left) * (value - arr[left]) / (arr[right]- arr[left]); int midVal=arr[mid]; if (value>midVal){ return insertValueSearch(arr,mid+1,right,value); }else if (value<midVal){ return insertValueSearch(arr,left,mid-1,value); }else { return mid; } } }

其他都和二分相同，只是修改了求mid的公式

测试：

public static void main(String[] args) { //必须是有序的 //int[]arr={0,1,2,3,4,5}; int arr[]=new int[100]; for (int i=0;i<100;i++){ arr[i]=i; } int i = insertValueSearch(arr, 0, arr.length - 1, 2); System.out.println(i); }

结果： count:1 2

只查了1次

同样，使用插值法也是有限制的：

1.对于数据量较大，关键字分布均匀的数据来说，采用插值查找, 速度较快. 2.关键字分布不均匀的情况下，该方法未必比折半查找要好