excel 模糊查找二分法自我理解

xia125602

二分法的概念

数学方面牛顿二分法

一般地，对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。

解方程即要求f(x)的所有零点。

假定f(x)在区间（x，y）上连续

先找到a、b属于区间（x，y），使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f[(a+b)/2],

现在假设f(a)<0,f(b)>0,a<b

①如果f[(a+b)/2]=0，该点就是零点，

②如果f[(a+b)/2]<0,则在区间（(a+b)/2，b)内有零点，(a+b)/2赋给a，从①开始继续使用中点函数值判断。

③如果f[(a+b)/2]>0，则在区间(a,(a+b)/2)内有零点，(a+b)/2赋给b，从①开始继续使用中点函数值判断。

这样就可以不断接近零点。当区间小于一定值时，结束迭代过程。

通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。

从以上可以看出，每次运算后，区间长度减少一半，是线性收敛。另外，二分法不能计算复根和重根。

先发上来个二分法的概念有助理解。（请勿插楼，谢谢）

xia125602

                                               Excel中二分法的应用
明白了上面二分法的意思，那运用在excel中match、lookup……等的模糊查找就好理解了。但在excel中的应用又和数学方面有些不同。
一、EXCEL和数学方面二分法的不同
1、这第一点的不同是在excel中所有能模糊查找的函数的第二个参数找不到零点，所以用中间值代替。
中间值等于数组最中间那个值。
偶数数组的中间值=数据个数/2 的值=counta(数组)/2的值。
奇数数组的中间值=(数据个数+1)/2的值= counta(数组)/2+1/2的值。
2、这第二点的不同是excel中数组中包含文本值、逻辑值、错误值。这些在模糊查找时会被忽略。
3、如果不规定取数精度的话，数学方面的二分法是永远查找不到值的，只能无限循环下去，有些专家就在说二分法是错误的（这里就不做讨论），在excel里面就没有这方面的考虑。

xia125602

二、Excel中二分法的具体算法
(这里就不做流程图了)
Exce中的二分法也和数学牛顿二分法的查找方式一样（线性迭代），用excel的查找值（函数第一个参数）与目标值（中间值）进行比较，这里就涉及到4种情况。

情况1：查找值和中间目标值相等
这时会依次从中间值向右判断是否有连续和中间值相等的最后一个值。
例：

xia125602

情况2：查找值小于中间目标值

  这时会以数组第一个值与中间置为区域进行查找。也就是以中间置为边界向左查找。

例:

=lookup(1,{1,2,1},{1,2,3})=1

①  第一次查找

中间值为2,查找值1<2,以2为边界向左查找

②  第二次查找

   就相当于=lookup(1,{1,2},{1,2}) 这时的中间值为1,等于查找值1.

③  第三次查找

   这时就和情况1相同了,依次向右判断时候存在连续的1，这题不存在，返回结果1

=lookup(,{1,2,1},{1,2,3})=#N/A

第一个参数省略，默认为0

①     第一次查找

中间值为2,查找值0<2,以2为边界向左查找

②     第二次查找

相当于=lookup(,{1,2},{1,2})，中间值1，查找值0<1,以1为边界向左查找，没数值，查找不到，出错。

情况3：查找值大于中间目标值

    这时会以数组中间置和数组最后一个值为区域进行查找。也就是以中间置为边界向右查找。和情况2相反。

xia125602

情况4：存在文本值、逻辑值、真空、假空和错误值的情况（以下描述成非纯数值型）。
这里的区别是：查找的中间值如果为文本值、真空、假空、逻辑值和错误值,中间值自动向右变动，直到中间目标值为纯数字为止，这时以这个数字为中间值和查找值进行判断。
例：
  C1=LOOKUP(17,A1:A19,B1:B19)  F1、H1、J1、M1、P1公式同理。

如下图：文本值、真空、假空、逻辑值、错误值的结果一致，原理一致。
①        第一次查找
   中间值为第10行的值（依次为：a、 、””、ture、#DIV/0!）,中间值不为纯数字，向右找取第一个纯数字为13，这时以13作为中间值。查找值17>13,属于情况3，以13为边界向右查找。
PS: I、J列单独剔出来讲

由于每小时限发5个帖子，所以暂请不要插楼，谢谢合作。

xia125602

②  第二次查找

以上图作为区域进行第二次查找，中间值为16对应的a，不为纯数字，中间值向右变动找到纯数字18，以18作为中间值，查找值17<18,此时关键点注意。由于非纯数值型全部被忽略，所以相当于就剩下{13,18}了。所以最后结果返回13对应的值。关键点：在查找中间值的前，非纯数值型是已经被忽略的了（原因好像是excel所有函数是先处理参数，然后再处理参数之间的运算的，这是我的理解，不知道对不对），但数组的个数是没有被忽略的，所以中间值还是要从数组最中间那个值判断起的，而且中间值必须要是一个纯数字才能进行判断。IJ列的情况：
①  第1次查找

中间值为第10行的0，查找值17>0,以中间值0为边界向右查找
②   第2次查找

中间值为14对应的0，查找值17>0, 以中间值0为边界继续向右查找
③   第3次查找

中间值为16对应的0，查找值17>0, 以中间值0为边界继续向右查找
④  第4次查找

中间值为17对应的0，查找值17>0, 以中间值0为边界继续向右查找
⑤   第5次查找

中间值为18，查找值17<18, 以中间值18为边界继续向左查找这时只有{0,18}，所以结果返回0所对应的17。

xia125602

最后一个问题。
我们常遇见的汉字字母数字混合取数字的问题：
例： 我爱你中国123    （要得到123）
一般公式为：=-lookup(,-right(a1,row($1:9)))
lookup的二个参数的结果为：{-3;-23;-123;#VALUE!;#VALUE!;#VALUE!;#VALUE!;#VALUE!;#VALUE!}
这时你会看到如果按照二分法解析的话，中间值是第5个，是个错误值，依次向右取一个纯数字，取不到。难道和情况4产生了矛盾。难道情况4解释不通？？
我的理解是，这时候的LOOKUP查找不是二分法查找，而是顺序查找，所以能返回结果。
最后的最后，上传一个例子加深对情况4的理解，该例子不做解释（愿意了解的兄台自己了解下结果）。

满坛皆为吾师

清晰明朗，拨云见月，之前也有几位前辈做过分析，对吾等还是过于高深了，顺便补上前辈的流程图
chrisfang


liuchengsw

醉眼看尘世

好贴，必须顶~

jacky1998

xia125602 发表于 2014-8-16 13:22
最后一个问题。
我们常遇见的汉字字母数字混合取数字的问题：
例： 我爱你中国123    （要得到123）

忽略错误值的函数不多。对于二元结构，LOOKUP是认定序列满足任何排序的。也就是说，如果查找值大于所有值，那么肯定会查到最后一个有效值(这样查找结果一般不满足最小的最大值）。只有在规则下查找不到任何有效值，结果才会出错，与被查找序列中的错误值无关（好比其它函数忽略逻辑值），LOOKUP函数的运行机制并不检测被查找序列的排序方式。
只有序列不满足升序，而查找值不大于所有序列有效值，查找结果会在二分查找到第一有效值邻近取值(这样查找结果一般不满足最小的最大值）。(查找结果一般不满足最小的最大值的前提是序列满足升序排序。至于错误值是否影响排序的有效性，大家可自测，换句话说，就是指全序列是否需要连续不中断升序排序）