尚硅谷Java数据结构--插值查找(二分查找改进)

在二分查找中：
$mid=(left+right)/2=left+\frac{1}{2}(right-left)$
而在插值查找中：
$mid=left+\frac{target-arr[left]}{arr[right]-arr[left]}(right-left)$

插值查找算法相对于二分查找可以更加精确的定位target所在的位置

以下是二分查找和插值查找的代码

package DataStructure;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86178
 * Date: 2024-02-29
 * Time: 12:44
 */
public class FindVal {
    static int binaryCnt=0;
    static int inserCnt=0;
    public static void main(String[] args) {
        int[] arr=new int[100];
        for(int i=0;i<arr.length;i++){
            arr[i]=i+1;
        }
        /*for (int i : arr) {
            System.out.print(i+" ");
        }*/
        //todo 返回下标
        System.out.println("查找数字1");
        System.out.println("二分查找下标返回"+BinarySearch(arr, 0, arr.length - 1, 1 ));
        System.out.println("二分查找调用次数："+binaryCnt);
        System.out.println("插值查找下标返回"+InsertSearch(arr, 0, arr.length - 1, 1 ));
        System.out.println("插值查找调用次数："+inserCnt);
    }
    public static int BinarySearch(int[] arr,int left,int right,int target){
        binaryCnt++;
        if(left>right)  return -1;
        
        int mid=(left+right)/2;
        if(target==arr[mid])    return mid;
        else if(target>arr[mid])    return BinarySearch(arr,mid+1,right,target);
        else return BinarySearch(arr,left,mid-1,target);
    }
    public static int InsertSearch(int[] arr,int left,int right,int target){
        inserCnt++;
        /*
        todo 其中 target<arr[0] || target>arr[arr.length-1] 的判断是必须的
             因为 mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
             当target非常大的时候 会出现下标越界
         */
        if(left>right || target<arr[0] || target>arr[arr.length-1])  return -1;

        int mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);
        if(target==arr[mid])    return mid;
        else if(target>arr[mid])    return InsertSearch(arr,mid+1,right,target);
        else return InsertSearch(arr,left,mid-1,target);
    }
}

其中插值查找需要注意mid下标越界问题

原文地址：https://blog.csdn.net/m0_70094411/article/details/136370940

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！