精华内容
下载资源
问答
  • Java插值查找算法

    2020-07-20 22:42:22
    import java.util.Arrays; public class InsertValueSearch { public static void main(String[] args) { int arr[] = { 1, 8, 10, 89,1000,1000, 1234 }; int index = insertValueSearch(arr, 0, arr....
    package com.tentact.search;
    
    import java.util.Arrays;
    
    public class InsertValueSearch {
    
    	public static void main(String[] args) {
    	
    		int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
    		
    		int index = insertValueSearch(arr, 0, arr.length - 1, 1234);
    		System.out.println("index = " + index);
    		
    		//System.out.println(Arrays.toString(arr));
    	}
    
    	//编写插值查找算法
    	//说明:插值查找算法,也要求数组是有序的
    	/**
    	 * 
    	 * @param arr 数组
    	 * @param left 左边索引
    	 * @param right 右边索引
    	 * @param findVal 查找值
    	 * @return 如果找到,就返回对应的下标,如果没有找到,返回-1
    	 */
    	public static int insertValueSearch(int[] arr, int left, int right, int findVal) { 
    
    		System.out.println("插值查找次数~~");
    		
    		//注意:findVal < arr[0]  和  findVal > arr[arr.length - 1] 必须需要
    		//否则我们得到的 mid 可能越界
    		if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
    			return -1;
    		}
    
    		// 求出mid, 自适应
    		int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
    		int midVal = arr[mid];
    		if (findVal > midVal) { // 说明应该向右边递归
    			return insertValueSearch(arr, mid + 1, right, findVal);
    		} else if (findVal < midVal) { // 说明向左递归查找
    			return insertValueSearch(arr, left, mid - 1, findVal);
    		} else {
    			return mid;
    		}
    
    	}
    }
    
    

    与二分查找类似,插值查找也需要目标数组必须为有序的数组,其关键的代码为int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);利用这行代码可以直接锁定到目标值的位置。

    展开全文
  • java插值查找代码实现

    2020-04-29 15:26:36
    import java.util.Arrays; /** * @author Drug * @create 2020-04-29 14:59 */ public class InsertValueSearch { public static void main(String[] args) { int[] arr = new int[100]; f...
    
    import java.util.Arrays;
    
    /**
     * @author Drug
     * @create 2020-04-29 14:59
     */
    public class InsertValueSearch {
        public static void main(String[] args) {
            int[] arr = new int[100];
            for(int i =0;i<arr.length;i++){
                arr[i] = i+1;
            }
            System.out.println(Arrays.toString(arr));
            int i = insertValueSearch(arr, 0, 99, 97);
            System.out.println(i);
        }
    
        /**
         * 插值查找
         * @param arr 数组
         * @param left 左界
         * @param right 右界
         * @param value 查找数值
         */
        public static int insertValueSearch(int[] arr,int left,int right,int value){
            System.out.println("这是插值查找~");
            //找不到或者越界判定
            if(left > right || arr[left] > value || arr[right] < value){
                return -1;
            }
            //中间数选择
            int mid = left + (right-left)*(value - arr[left])/(arr[right] - arr[left]);
            int midValue = arr[mid];
            //判断
            //查找值小于中间值
            if(value < midValue){
                return insertValueSearch(arr,left, mid-1, value);
            }else if(value > midValue){
                //查找值大于中间值
                return insertValueSearch(arr,mid+1,right,value);
            }else{
                //找到了
                return mid;
            }
        }
    }
    
    
    展开全文
  • java实现插值查找

    2020-10-12 21:07:50
    什么是插值查找 插值查找,有序表的一种查找方式。 插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。 插值类似于平常查英文字典的方法,在查一个以字母C开头的英文单词时,决不会用二分查找...

    什么是插值查找

    • 插值查找,有序表的一种查找方式。
    • 插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率
    • 插值类似于平常查英文字典的方法,在查一个以字母C开头的英文单词时,决不会用二分查找,从字典的中间一页开始,因为知道它的大概位置是在字典的较前面的部分,因此可以从前面的某处查起,这就是插值查找的基本思想
    • 插值查找除要求查找表是顺序存储的有序表外,还要求数据元素的关键字在查找表中均匀分布,这样,就可以按比例插值。

    思路分析

    插值查找的实现和二分查找基本一致,唯一的区别就是查找点下标的选择。
    在这里插入图片描述
    其中,key为待查找关键字,low为待查找区间左端,high为待查找区间右端,mid为自适应查找点

    1. 计算mid
    2. 如果key==a[mid],返回mid
    3. 如果key>a[mid],进入右边区间继续查找
    4. 如果key<a[mid],进入左边区间继续查找

    插值查找代码实现

    /**
         * 插值查找(递归实现)
         *
         * @param arr  数组
         * @param low  待查找区间的左指针
         * @param high 待查找区间的右指针
         * @param key  待查找的关键字
         * @return 查找到的值的下标
         */
        public static int insertSearch(int[] arr, int low, int high, int key) {
            if (low > high) {
                return -1;
            }
            findCount++;
            // 根据待查找值key,计算出
            int mid = low +  (high - low) * (key - arr[low]) / (arr[high] - arr[low]);
            int midVal = arr[mid];
            if (key == midVal) {
                return mid;
            } else if (key > midVal) { // 到右边区域检索
                return insertSearch(arr, mid + 1, high, key);
            } else { // 到左边区域继续检索
                return insertSearch(arr, low, mid - 1, key);
            }
        }
    

    注意事项

    • 插值查找适用于均匀分布的查找表
    • 对于分布不均匀的查找表,其不一定适用
    展开全文
  • Java实现插值查找

    2020-04-17 10:51:07
    一、什么是插值查找 插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。 二、算法...

    一、什么是插值查找

    插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。

    二、算法要求

    1. 查找表是顺序存储的有序表
    2. 数据元素的关键字在查找表中均匀分布

    三、查找过程

    类似于二分查找,不同的是插值查找每次从自适应选择处开始查找

    1. 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;
    2. 否则利用 中间值加上一定的算法的位置 将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
    3. 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    四、代码实现

    public class InsertValueSearch {
    
        public static void main(String[] args) {
            int[] array = new int[100];
            for (int i = 0; i < 100;i++){
                array[i] = i+1;
            }
    
            int resultIndex = insertValueSearch(array,0,array.length-1,86);
            System.out.println("下标为:"+resultIndex);
        }
    
        /**
         * @param arrays 有序数组
         * @param left 最小索引
         * @param right 最大索引
         * @param findValue 查找值
         * @return 查找值的下标
         */
        public static int insertValueSearch(int[] arrays,int left,int right,int findValue){
            //判断是否继续进行
            if(left > right || findValue < arrays[0] || findValue > arrays[arrays.length-1]){
                return -1;
            }
    
            //自适应查找mid
            int mid = left + (right - left) * (findValue - arrays[left]) / (arrays[right] - arrays[left]);
            int midValue = arrays[mid];
    
            //查找值大于标志值则向右递归查询
            if(findValue > midValue){
                return insertValueSearch(arrays, mid + 1, right, findValue);
            }
            else if(findValue < midValue){
                return insertValueSearch(arrays, left, mid - 1, findValue);
            }
            else{
                return mid;
            }
        }
    }
    
    
    展开全文
  • Java插值查找算法

    2020-08-27 23:20:57
    插值查找算法相当于二分查找的优化版 应用场景: ①对于数据量较大,关键字分布比较均匀的查找表来说,采用 插值查找,速度较快 ②关键字分布不均匀的情况下,该方法不一定比折半查找要好 注意:插值查找算法,也要求...
  • java实现插值查找算法

    2019-09-06 10:13:48
    // 插值查找是二分查找的改进,mid的值用自适应的方法求得 // 对于数据量较大,关键字分布比较均匀的查找表来说采用插值查找速度较快 // 关键字分布不均匀(跳跃性很大)的情况下,该方法不一定比折半查找要好 public ...
  • 下面带来Java版本插值查找算法的实现,本篇一些概念沿用上一篇博客,入数组左索引为left,右索引为right。先说明一下,插值查找算法要求待查找的数组为有序的。 插值查找原理: 1.插值查找算法类似于二分查找,...
  • 插值查找 斐波那契查找 树表查找 分块查找 哈希查找 索引查询 深度搜索&&广度搜索 一、二分查找 int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 ...
  • 插值查找一、基本思路二、算法分析三、代码实现 一、基本思路 插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择...
  • Java基础查找算法(3)——插值查找(插入查找) 1.插值排序简述 插值查找,又称插入查找,与二分查找类似,需要所查数组已经有序,只是对mid下标的选取有所不同而已。 Java基础查找算法(2)——二分查找(折半查找) 二分...
  • 插值查找Java

    2020-03-20 16:22:16
    插值查找Java插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。 适用条件:...
  • java复习值插值查找

    2020-06-06 20:54:35
    插值查找 package learn; /** * 插值查找,二分查找的升级 * num是要查找的值 * mid=left+(right-left)*(num-array[left])/(array[right]-array[left]) */ public class InsertSearcj { public static int ...
  • 插值查找-Java

    2020-04-16 22:36:31
    1. 插值查找 1.1 插值查找的基本介绍 2. 代码演示 3. 适用场景 1. 插值查找 1.1 插值查找的基本介绍 与二分查找基本相似,就是 mid 的值不一样 2. 代码演示 package xmht.datastructuresandalgorithms....
  • 插值查找算法-Java

    2020-02-22 22:19:11
    插值查找算法
  • 插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。 插值查找公式:mid = left+ ...
  • 1、插值查找算法 Insert Value Search:是二分查找算法的改进版,二分查找的指针 mid 每次都只能折中取,插值查找算法对此做了一些改进,能根据待查找的数值对mid做自适应调整,从而加快查找速度。 步骤: 与...
  • 查找--插值查找Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢! 介绍 插值查找算法类似于二分查找,不同的是插值查找每次从...
  • import java.util.Arrays;import java.util.LinkedList;import java.util.List;/*** @author: Inki* @email: inki.yinji@qq.com* @create: 2020 1113* @last_modify: 2020 1113*/public class MyFind {...
  • 二分法查找与插值查找 两者的区别仅仅是中间值mid的不同,插值查找一般用于比较均匀的数据; import java.util.Arrays; public class SearchTest { public static void main(String[] args) { // TODO Auto-...
  • 前奏:插值查找是一种对折半查找算法的一种升级版,也是一种自适应查找算法(按照对应查找的值,设置对应的比例中间值查找) 思路 核心思路就是,当前元素位置差 left + (right - left) * (findVal - arr[left]) / ...
  • 顺序查找、二分查找、插值查找、斐波那契查找
  • 插值查找实现(java

    2020-09-29 22:48:26
    插值查找原理: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找 将折半查找中的求mid索引的公式,low表示左边索引 left , high表示右边索引 right, key就是待查找的值 value int mid = ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 393
精华内容 157
关键字:

java插值查找

java 订阅