算法-插值查找

程序员文章站 2022-07-12 09:28:57

...

插值查找是二分查找的一种变体，因此，插值查找的前提也是：待查找的数组必须是有序的！

插值查找对二分查找中mid的计算做了一些改进

传统的二分查找中对mid的计算：mid = (left + right) / 2 = left + 1/2 * (right - left)

插值查找中mid的计算：mid = left + ( (value -arr[left]) / (arr[right] - arr[left]) ) * (right - left)

其中，mid是数组的中间下标，left是数组第一个元素的下标，right是数组最后一个元素的下标，value是所要查找的值，arr是所要查找的数组

为什么要做这样的改变呢？

假设我们现在的数组为{1,2,3,4,5,6,7,9,10,11,12,13,14,15,16,17,18,19,20}，我们想找到1对应的下标
如果我们用传统的二分查找，每次计算的mid都是折半的结果（mid为中点），想找到1就得多折半几次，这样效率自然不高
若是用的插值查找，每次计算mid的时候value(所要查找的值)都是作为mid公式的一个变量，也就是说mid与value是有关系的，我们不再盲目死板地按照折半来得到mid，而是根据value的大小，动态地计算出mid( (value -arr[left]) / (arr[right] - arr[left]) 公式中的这部分是关键，这样计算出来的mid可以更接近value的下标）

算法代码


import java.util.Arrays;

public class InsertSearch {
	private static int[] myArr;

	private InsertSearch() {
	}

	public static InsertSearch instance(int[] arr) {
		myArr = arr;
		return new InsertSearch();
	}

	/**
	 * 
	 * @Title: insertSearch
	 * @Description: 递归实现插值查找
	 * @param: @param
	 *             left 当前所要查找的数组的第一个元素的下标
	 * @param: @param
	 *             right 当前所要查找的数组的最后一个元素的下标
	 * @param: @param
	 *             value 所要查找的值
	 * @return: int 所要查找的值在数组中的第一个下标，若找不到，则返回-1
	 */
	private int insertSearch(int left, int right, int value) {
		
		System.out.println("insertSearch查找中。。。");
		
		//如果所查找的值小于数组最小值或大于最大值，就返回-1，
		//这一步不可省略，省略会导致计算mid时下标越界（由于value参与到了mid的计算）
		if(value < myArr[left] || value > myArr[right])return -1;
		
		// 如果当前数组不为空
		if (left <= right) {
			int mid = left + ( (value - myArr[left]) / (myArr[right] - myArr[left]) ) * (right - left);// 计算mid
			// 如果所要查找的值比mid下标对应的值小，那么要向数组的左半部分进行查找
			if (value < myArr[mid]) {
				right = mid - 1;
				return insertSearch(left, right, value);
			} else if (value > myArr[mid]) {// 如果所要查找的值比mid下标对应的值大，那么要向数组的右半部分进行查找
				left = mid + 1;
				return insertSearch(left, right, value);
			} else {// 如果所要查找的值与mid下标对应的值相同，就返回mid
				return mid;
			}
		}

		// 若所要查找的数组为空，则返回-1
		return -1;
	}

	

	/**
	 * 
	 * @Title: insertSearch 
	 * @Description: 插值查找入口 （返回所查找值的第一个下标）
	 * @param: @param value 所要查找的值 
	 * @return: int 查找的值在数组中的下标，没有找到则返回-1
	 */
	public int insertSearch(int value) {
		return insertSearch(0, myArr.length - 1, value);
	}
	
}