什么是差值查找?

1.插值查找与二分查找很类似,都是用于在有序的基础上查找某个元素

2.二分查找的原理是,每次都取一半,然后与mid值比较,再决定下一次查找的范围

3.设想在一本英文字典里查找某个单词,因为是根据字母序排列好的,你不会傻到采用二分查找的方法,先找到这本字典的一半,再取这本字典的四分之一...这样下去比较吧,这种效率显然不是最快的,此时就轮到我们的差值查找出场了.

4.差值公式的推导:

有序序列: 1 2,3,4,5,6,7,8,9,10

比例公式:   假设数组a[i]已经有序

(key-low)/a[key]-a[low] =(high-low)/a[high]-a[low];

key-low=(high-low) *(a[key]-a[low])/a[high]-a[low];

key =low +(high-low) *(a[key]-a[low])/a[high]-a[low];

将key替换为mid,即第key个位置,此时是需要比较的位置,是mid,a[key]替换为key,要查找的值,即我们要查找位置为mid上的是否等于key

mid =low +(high-low) *(key-a[low])/a[high]-a[low];

5.差值查找需要满足的两个条件:

a.每一次对数据的访问与通常的指令相比,费用都是相当昂贵的。例如,待查找的表一定是在磁盘而非内存中,因而每一次比较都要进行磁盘访问。此时查找查找的效率优势就可以明显体现出来

b.  数据表有序,且均匀分布,如电话簿,字典即是均匀分布的.例如{1 2,3,4,5,6,7,8,9,10}是均匀分布,而{1,3,7,11,16,21,27...}就不是均匀分布的.此时使用差值查找和二分查找比较的话,优势体现不明显.

代码如下:

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
int Bin_Search(int *a, int key, int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); //此处于二分查找不同,套用插值公式
        if (a[mid] > key)         //如果key比插值小,把高位调整为插值下标的下一位
            high = mid - 1;
        else if (a[mid] < key)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}
int mainA()
{
    int a[] = { 1, 5, 17, 25, 33, 38, 46, 55, 69, 75, 99 };
    int key;
    int len = sizeof(a) / sizeof(*a);
    printf("请输入要查找的值:\n");
    scanf("%d", &key);
    int pos = Bin_Search(a, key, len);
    if (pos != -1)
        printf("在数组的第%d个位置找到:%d\n", pos + 1, key);
    else
        printf("未在数组中找到元素:%d\n", key);

    system("pause");
    return 0;
}
时间: 11-02

什么是差值查找?的相关文章

查找(哨兵查找、二分查找、差值查找)

#include <iostream> using namespace std; #define N 10 int fib(int n) { if(n == 0) { return 0; } else if(n == 1) { return 1; } else { return (fib(n-1) + fib(n-2)); } } //普通查找: int sequenctial_Search(int *a,int n,int key) { int i; a[0] = key; i = n; w

二分查找的改进--差值查找

差值查找 在二分查找中,我们每次比较都可以排除一半的数据量,这个已经是很高效了.如果利用关键字本身的信息,每次排除的数据量充分依赖于关键字的大小,则查找会更高效,这就是差值查找的思想. 下面通过示例代码,比较二分查找和差值查找的不同,在不同中领略差值查找的改良之处. #include <stdio.h> #include <stdlib.h> int InterSearch(int *array, int n, int key) { if (array && n &

hdu1598find the most comfortable road(并查集+枚举,求起点到终点的边中最大边减最小边差值最小)

Problem Description XX星有许多城市,城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构)进行交流,每条SARS都对行驶在上面的Flycar限制了固定的Speed,同时XX星人对 Flycar的"舒适度"有特殊要求,即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求,flycar必须瞬间提速/降速,痛苦呀 ), 但XX星人对时间却没那么多要求.要你找出一条城市间的最舒适的路径.(

阿里 2014-08-29 校招机试题 求一个存放整数的二叉树相差最大的两节点差值绝对值

题目:写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这颗二叉树中相差最大的两个节点间的差值绝对值.请注意程序效率. 如果是数值之差,感觉怎么着也得遍历一遍,直接修改下二叉树的基本遍历代码就可以. #include<stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node * left; struct Node * right; } BitNode, *BiTree; /* 求

Houdini中给火花渲染准确的运动模糊 - 给运动模糊做非线性差值的方法以及固定粒子点数的方法

估计大家都知道使用运动速度来进行运动模糊的渲染,但是往往这个方法得到的运动模糊都是线性变化的,虽然乍一看没什么问题,但是如果想要每一帧的模糊轨迹也是有曲线变化的而不是僵硬的直来直去的话,使用trail算个速度来做的运动模糊是永远做不到这一点的. 这里我想通过常用的火花(spark)的运动模糊来讲一讲我所了解的一些比较好的方法. 所谓渲染中的运动模糊无非就是差值算法.目前使用的比较多的主要有两种.第一种就是上面说到的直接使用速度来线性差值,这种方法会计算每一个点的速度方向,计算出前一帧或者后一帧的

华为机试—差值排序

对整形数组按照和指定整数的差值大小进行排序,按照差值升序排列返回. 要求实现方法: public staticint[] calcTimes(int[] num, int value); [输入] num:整型数组: value 指定的整数 [返回] 按照升序返回整型数组,排序按照各个整数和指定整数的差值大小 [注意]只需要完成该函数功能算法,中间不需要有任何IO的输入输出 示例 输入:num = {1,2,3,4,5,10,17,18,19}  value = 5 返回:{5,4,3,2,1,

差值的再议-Hermite差值

1. 插值法 插值法又称"内插法",是利用函数f (x)在某区间中已知的若干点的函数值,作出适当的特定函数,在区间的其他点上用这特定函数的值作为函数f (x)的近似值,这种方法称为插值法. 如果这特定函数是多项式,就称它为插值多项式. 2. 经典的Hermite差值 Hermite插值是利用未知函数f(x)在插值节点上的函数值及导数值来构造插值多项式的.因此,Hermite插值满足在节点上等于给定函数值,而且在节点上的导数值也等于给定的导数值. 对于高阶导数的情况,Hermite插值多

基于Qt的OpenGL可编程管线学习(17)- 差值、反差值、排除

1.差值 shader //差值 uniform sampler2D U_MainTexture; uniform sampler2D U_SubTexture; varying vec2 M_coord; void main() {         vec4 blendColor = texture2D(U_SubTexture, M_coord);         vec4 baseColor = texture2D(U_MainTexture, M_coord);         gl_F

九度oj 题目1096:日期差值

题目描述: 有两个日期,求两个日期之间的天数,如果两个日期是连续的我们规定他们之间的天数为两天 输入: 有多组数据,每组数据有两行,分别表示两个日期,形式为YYYYMMDD 输出: 每组数据输出一行,即日期差值 样例输入: 20110412 20110422 样例输出: 11 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <string> 5 #include

求二叉树中相差最大的两个节点间的差值绝对值

题目描述: 写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这棵二叉树中相差最大的两个节点间的差值绝对值.请注意程序效率. solution: int findMinMax(BTNode *T) { if(!T) return 0; int max = INT_MIN; int min = INT_MAX; stack<BTNode*> s; s.push(T); while (!s.empty()) { BTNode *tmp = s.top(); if(tmp->d