blocks|key|786266|text|您可以将数组arr看作是一个作用于索引并返回值的函数f，它是单调的(因为数组是排序的)。所以您有您的初始数据f(low)+=+m和f(high)+=+M。现在你可以用一条直线插值你的函数f，这是相当合理的，因为你的f是单调的，你只有2分。因此，你的插值应该是线(线性函数)，通过抛点，(low,+m)和(high,+M)。这是方程|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|786267|(y+-+f(low))/(f(high)+-+f(low))+=+(x+-+low)/(high+-+low)|code-block|syntax|javascript|786268|所以这里的y是搜索空间的元素，x来自域(x是数组的索引)。因此，如果您的函数f与它的插值相同，那么key的索引将是：|786269|x+=+low+%2B+(high+-+low)*(key+-+f(low))/(f(high)+-+f(low))|786270|因此，假设您的函数f接近它的插值，您应该检查x的值f，看看它是否是目标。否则，你只需缩小你的插值间隔。|786271|entityMap^0|6|3|Q|1|1I|A|1T|B|2L|1|2Z|1|3Y|8|47|9|0|0|5|1|F|1|12|1|1D|3|0|0|9|1|M|1|P|1|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]|$9|11|A|12|B|C]|$9|13|A|14|B|C]|$9|15|A|16|B|C]|$9|17|A|18|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|19|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|1A|8|@$9|1B|A|1C|B|C]|$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]|$9|1H|A|1I|B|C]]|D|@]|E|$]]|$1|M|3|N|5|H|7|1J|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|1K|8|@$9|1L|A|1M|B|C]|$9|1N|A|1O|B|C]|$9|1P|A|1Q|B|C]]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|1R|8|@]|D|@]|E|$]]]|R|$]]

You can think of array <code>arr</code> as a function <code>f</code> that acts on index and return a value, which is monotone (because array is sorted). So you have your initial data <code>f(low) = m</code> and <code>f(high) = M</code>. Now you can interpolate your function <code>f</code> with a straight line, which is quite reasonable to do because your <code>f</code> is monotone and you have only 2 points.
So your interpolation should be line (linear function) that pass throw points <code>(low, m)</code> and <code>(high, M)</code>. This is it's equation

<pre><code>(y - f(low))/(f(high) - f(low)) = (x - low)/(high - low)
</code></pre>

So <code>y</code> here is the element of search space and <code>x</code> is from domain (x is index of array). So if your function <code>f</code> would be the same as it's interpolation, then index of your <code>key</code> would be:

<pre><code>x = low + (high - low)*(key - f(low))/(f(high) - f(low))
</code></pre>

So, assuming that your function <code>f</code> is close to it's interpolation, you should just check the value <code>f</code> at <code>x</code> to see if it is the goal. Otherwise you just shrink your interpolation interval.

blocks|key|40191|text|扩展到@+answer+-另一个有趣的答案|type|unstyled|depth|inlineStyleRanges|entityRanges|data|40192|他提出的方程是基于插值公式+(一条线的方程)。|offset|length|40193|blockquote|40194|📷|atomic|40195|现在，将f()视为接受索引并返回其y轴值的函数，|style|CODE|40196|y1+=+f(low)
y2+=+f(high)
x1+=+low
x2+=+high

(y+-+f(low))+=+[(f(high)+-+f(low))+/+(high+-+low)]+*+(x+-+low);

OR

x+=+low+%2B+[(high+-+low)+*+(y+-+f(low))]+/+(f(high)+-+f(low))

here:+y+=+key
we+are+looking+for+position(value)+of+x.|code-block|syntax|javascript|40197|entityMap|0|LINK|mutability|MUTABLE|url|http://formulas.tutorvista.com/math/interpolation-formula.html|1|IMAGE|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/065dc818961143eedeba3d18af3a6166.png|imageAlt^0|0|9|4|0|0|0|0|1|1|0|4|3|H|1|0|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@]|9|@$D|19|E|1A|1|1B]]|A|$]]|$1|F|3|-4|5|G|7|1C|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|1D|8|@]|9|@$D|1E|E|1F|1|1G]]|A|$]]|$1|K|3|L|5|6|7|1H|8|@$D|1I|E|1J|M|N]|$D|1K|E|1L|M|N]]|9|@]|A|$]]|$1|O|3|P|5|Q|7|1M|8|@]|9|@]|A|$R|S]]|$1|T|3|-4|5|6|7|1N|8|@]|9|@]|A|$]]]|U|$V|$5|W|X|Y|A|$Z|10]]|11|$5|12|X|13|A|$14|15|16|-4]]]]

An extention to @JustAnotherCurious answer

the equation perposed by him was based on <a href="http://formulas.tutorvista.com/math/interpolation-formula.html" rel="noreferrer">Interpolation Formula</a> (equ of a line) 

<blockquote>
 <a href="https://i.stack.imgur.com/Rc2bO.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Rc2bO.png" alt="enter image description here"></a>
</blockquote>

Now, think<code>f()</code> as function that takes an index and return its <code>y</code> axis value, 

<pre><code>y1 = f(low)
y2 = f(high)
x1 = low
x2 = high

(y - f(low)) = [(f(high) - f(low)) / (high - low)] * (x - low);

OR

x = low + [(high - low) * (y - f(low))] / (f(high) - f(low))

here: y = key
we are looking for position(value) of x.
</code></pre>

I came to know that Interpolation Search is a modification of Binary Search where in binary search the input is divided into two equal halves in each iteration by computing 

<pre><code>mid = (low + high) / 2
</code></pre>

and in Interpolation search the mid is computed as

<pre><code>mid = low + (key - arr[low]) * ((high - low) / (arr[high] - arr[low]))
</code></pre>

Now I need to understand this formula of calculating <code>mid</code> in interpolation search.

Ref: <a href="https://en.wikipedia.org/wiki/Interpolation_search#Sample_implementation" rel="noreferrer">https://en.wikipedia.org/wiki/Interpolation_search#Sample_implementation</a>

Computing mid in Interpolation Search?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我知道插值搜索是对二进制搜索的一种改进，在二进制搜索中，通过计算，输入在每次迭代中被分成两等份。mid = (low + high) / 2在插值搜索中，中间值被计算为mid = low + (key - arr[low]) * ((high - low) / (arr[high] - arr[low]))现在我需要理...

问插值搜索中的中间计算？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问插值搜索中的中间计算？EN