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

    千次阅读 2020-04-29 18:10:31
    插值查找,有序表的一种...1)插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid处开始查找。 2)将折半查找中的求 mid索引的公式 , low表示左边索引 left, high表示右边索引 righ...

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

    1)插值查找原理介绍:
    插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid处开始查找。

    2)将折半查找中的求    mid索引的公式   , low表示左边索引   left, high表示右边索引  right.
    key就是前面我们讲的     findVal
     

    插值查找的前提是有序数列元素的值是成线性增长的(这个假设的精确度会影响算法的效率,但不会影响算法的正确性)。对于大多数有序数列来说,这前提是可以成立的。我们不妨假设它就是成立的,那样,当我们知道一个要查找值的大小后。就可以根据数列线性增长的性质,求出要查找的值在数列中的大概位置

    比如说在数列A[lo,hi)中查找e。我们设e的下标为mi。由于数列线性增长,我们不难得到这个等式:


            进而得出:

     

    package com.atguigu;
    
    public class InsertValueSearch {
    
    	public static void main(String[] args) {
    
    
    		int arr[] = { 1, 8, 10, 89,1000, 1234 };
    
    		int index = insertValueSearch(arr, 0, arr.length - 1, 1000);
    
    		System.out.println("index = " + index);
    
    	}
    	//编写插值查找算法
    	//说明:插值查找算法,也要求数组是有序的
    	/**
    	 *
    	 * @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;
    		}
    
    	}
    }
    

     

    时间复杂度

    插值查找的时间复杂度也是O(logN)O(logN)。

    注意事项

    1. 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
    2. 关键字分布不均匀的情况下,该方法不一定比折半查找要好
    展开全文
  • 查找算法之插值查找

    2020-08-10 09:07:08
    1) 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找 2)他与二分查找的最大区别就是这个mid的定义,使得在基本连续的有序数据中,插值查找会比二分查找优秀。 int mid ...

    查找算法之插值查找

    1) 插值查找原理介绍:

    插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找
    2)他与二分查找的最大区别就是这个mid的定义,使得在基本连续的有序数据中,插值查找会比二分查找优秀。
    int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);

    public class InsertValueSearch {
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int arr[] = { 1, 3, 5, 7, 8, 9, 100, 1234 };
    		int insertValueSearch = insertValueSearch(arr, 0, arr.length - 1, 3);
    		System.out.println(insertValueSearch);
    	}
    	// 定义查找查找方法
    	public static int insertValueSearch(int arr[], int left, int right, int findVal) {
    		// 在插值查找中,findVal<arr[0] || findVal>arr[arr.length-1]是必须的,否则mid可能越界
    		if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
    			return -1;
    		}
    		int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
    		int midVal = arr[mid];
    		if (midVal < findVal) {// 向右边递归
    			return insertValueSearch(arr, mid + 1, right, findVal);
    		} else if (midVal > findVal) {// 向右递归
    			return insertValueSearch(arr, left, mid - 1, findVal);
    		} else {// 找到了
    			return mid;
    		}
    	}
    }
    
    展开全文
  • 【查找】插值查找

    2020-10-13 15:08:40
    1、插值查找原理介绍 (1)插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。 (2)将折半查找中的求mid 索引的公式 , low 表示左边索,high表示右边索引,key 就是要查找的值 这里要...

    1、插值查找原理介绍

    (1)插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。

    (2)将折半查找中的求mid 索引的公式 , low 表示左边索,high表示右边索引,key 就是要查找的值

    这里要提一下,插值查找的前提是数组是有序的。

    (3)举例说明插值查找算法 1-100 的数组

    数组 arr = [1, 2, 3, ......., 100]。假如我们需要查找的值 1,使用二分查找的话,我们需要多次递归,才能找到 1。

    使用插值查找算法

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

    int mid = 0 + (99 - 0) * (1 - 1)/ (100 - 1) = 0 + 99 * 0 / 99 = 0

    比如我们查找的值 100

    int mid = 0 + (99 - 0) * (100 - 1) / (100 - 1) = 0 + 99 * 99 / 99 = 0 + 99 = 99

    2、插值查找应用案例

    请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下标,如果没有就返回-1。

    //【默认升序】
    	//差值查找
    	//如果找到就返回对应的下标,如果没有找到,就返回-1
    	public static int insertValueSearch(int[] arr,int left,int right,int findValue){
    		
    		System.out.println("Hello");
    		
    		//退出条件
    		//findValue < arr[0]和findValue > arr[arr.length - 1]必须有
    		//否则mid 可能越界
    		if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) {
    			return -1;
    		}
    		//求出mid
    		int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
    		int midValue = arr[mid]; 
    		
    		if (findValue > midValue) {
    			// 向右递归
    			return insertValueSearch(arr, mid + 1, right, findValue);
    		} else if (findValue < midValue) {
    			return insertValueSearch(arr, left, mid - 1, findValue);
    		} else {
    			return mid;
    		}
    
    	}

    3、插值查找注意事项

    (1)对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快;

    (2)关键字分布不均匀的情况下,该方法不一定比折半查找要好。

    展开全文
  • 插值查找算法

    2020-03-14 12:25:04
    插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 ...

    插值查找算法(有序数组)

    1. 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。
    2. 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引 right. key 就是前面我们讲的 findVal
      在这里插入图片描述
    3. int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/
      对应前面的代码公式:
      int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) 4) 举例说明插值查找算法 1-100 的数组
      在这里插入图片描述

    插值查找注意事项:

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

    插值查找应用案例:
    请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ,输入一个数看看该数组是否存在此数,并且求出下 标,如果没有就提示"没有这个数"。
    代码实现:

    package com.atguigu.search;
    
    /* 二分(折半)查找条件:有序数组。
     * 
     * */
    public class BinarySearch {
    
    	public static void main(String[] args) {
    		
    		int[] arr = {2,4,6,78,90};
            
    		//不考虑有重复元素的查找。
    		int index =insertValueSearch(arr,0,arr.length-1,26);
    		
    		System.out.println(index);
    	}
    
    	
    	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;
    		}
    
    	}
    
    }
    
    
    展开全文
  • 插值查找算法实战

    2021-03-13 20:45:35
    插值查找原理 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。 二插值查找公式 将二分查找中的求 mid 索引的公式进行改造 , low 表示左边索引 left, high 表示右边索引 right,...
  • 查找算法:插值查找

    2020-09-07 09:56:12
    插值查找原理: 其中key就是我们要查找的数,相当与在二分法中讲到的findVal。 (插值查找算法也要求数组是有序的) 代码实现 public class InsertSearch { public static void main(String[] args) { int [] arr...
  • 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引 int mid = low + (high - low) * ...
  • <!-- TOC --> <li><a href="#1-%E6%8F%92%E5%80%BC%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95">1. 插值查找算法
  • (1)插值查找原理(注意轴点mi的计算公式) (2)插值查找案例 (3)插值查找性能分析 (4)查找算法比对
  • 插值查找原理介绍: 1)插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找 2)将折半查找中的求mid 索引的公式, low表示左边索引, high表示右边索引. 3)int midindex =low + (high-low) *...
  • 前面介绍的二分查找,其复杂度为O(logn),在数据量较多的情况下比顺序查找效率高很多:机器学习入坑者:二分查找原理及python与C++实现详解​zhuanlan.zhihu.com 当然,二分查找要求数据必须是有序的,这也...
  • 插值查找实现(java)

    2020-09-29 22:48:26
    插值查找原理: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找 将折半查找中的求mid索引的公式,low表示左边索引 left , high表示右边索引 right, key就是待查找的值 value int mid = ...
  • 插值查找基本介绍 插值查找算法类似于二分查找, 不同的是插值查找每次从自适应 mid 处开始查找。 插值查找图解 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left ,high 表示右边索引 right ,key 就是...
  • 插值查找原理: 1.插值查找算法类似于二分查找,不同的是插值查找每次从只适应的mid处开始查找; 2.在二分查找中,求mid的公式为: 插值算法将求mid的公式改进为: 对应的代码为:int mid = left + (right - ...
  • 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。 公式推导: 代码实现: package com.athome.search; /** * Description: * Author:江洋大盗 * Date:2021/1/21...
  • 插值查找 原理介绍 1)插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。 2)将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right. key 就是前面我们讲的 ...
  • 查找算法 - 插值查找

    2021-01-09 15:03:11
    插值查找,有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。 时间复杂度 O(loglogN) 思路...
  • 插值查找原理介绍: 插值查找算法类似于二分查找,不同的是插值查找每次从自适应 mid 处开始查找。 将折半查找中的求 mid 索引的公式 , low 表示左边索引 left, high 表示右边索引;right. key 就是前面我们讲的 ...
  • 插值查找算法类似二分法查找,不同的是插值查找每次从自适应的mid值开始查找。 插值插值的求mid索引的公式: int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) 插值查找也...
  • 数据结构-- 向量--插值查找

    千次阅读 2015-12-01 19:19:58
    我们来看一下插值查找。 本页内容  1.插值查找原理  2.代码实现  3.总结评价

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 205
精华内容 82
关键字:

插值查找原理