chrisfang的Excel大全

LOOKUP函数的二分法查找策略

2012-05-24
作者: chrisfang | 分类: Excel函数公式 | 阅读: 4,436 次浏览 | Tags:
声明: 本站文章均属原创,转载时请标明出处

二分法查找又称折半查找,它是一种效率较高的查找算法。二分法通常要求目标数组中的数据是有序排列的。LOOKUP函数所使用的查找策略就是二分法,不仅仅是LOOKUP,其实VLOOKUP  HLOOKUP函数在其第四参数为True时、MATCH函数在其第三参数为1时也都是遵循了二分法的查找原则来进行运算的。

二分法的具体方法,通常会通过下面这个流程图来表达:

 LOOKUP函数的二分法查找策略

 

但流程图过于抽象,为了让这个查找过程更容易理解,尝试使用其他方法再进行一些解读。

首先是算法文字描述:

1, 将查找值与目标向量中的“中位值”进行对比

2, 大于中位值时,以中位作为边界,继续在其右侧取新的中位值继续对比

3, 小于中位值时,以中位作为边界,继续在其左侧取新的中位值继续对比

4, 等于中位值时,依次判断其右侧数值是否继续相等,直到不相等时返回最后一个相等的数值

5, 当中位位置与边界重叠时,中止对比,此时如果查找值大于中位值,则返回中位值;如果查找值小于中位值,则返回中位左侧数值。如果左侧数值不存在,返回#N/A

 

注:上面提到的“中位值”指的是目标数组中位置居中的数据(数据个数为偶数时,中位等于个数除以2;数据个数为奇数时,中位等于<个数+1>除以2),与统计学上传统意义上的中位值不完全相同

 

再配合下面两张运算过程图加深理解:

LOOKUP函数的二分法查找策略

LOOKUP函数的二分法查找策略

 

最后,再提供一个自动演示查找运算过程的Excel文档:

LOOKUP函数的二分法查找策略

微盘下载:http://vdisk.weibo.com/s/5OZjg/1337825337 

本地下载: LOOKUP二分法查找演示 (807)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>