奇怪的发现lookup 0分法的规率(学习与讨论)

jsxjd

笑着...两年过去 发表于 2013-8-11 10:52
不大明白你的意思，
好吧，是我理解能力不够好，我可以理解成：直接给你两个结果 or 把大师们分析的二分 ...

总之把握一个原则：“遵循规则”
要彻底解析LookUp，要进一步研究以下几点：
1、两分的索引是向上还是向下舍入？
2、生成索引时，分隔点本身是否也计入？
3、不匹配时，即“大于/小于”时如何取向？

Bodhidharma

论坛里有几位大师版主深深的研究过lookup的二分法运算过程及规率，我的理解是：①所有二分法，第一参数只能是2.如lookup(2,….②如果数据是升序排列，那么从左到右找，找到>=本身时停止并返回对应的数值(有第三个参数时)或者返回>=本身的那个值(没有第三个参数时).③当乱序的时候，从中间向右边找(包含中间值)先找左边第一个值，如果<=本身，则返回对应值，否则去右边找，找到<=本身时返回对应值。。。[当然在找的时候都是跳过错误值]

呃…從這段話來看，樓主似乎對LOOKUP和二分法有很大的誤解，建議樓主搜尋一下「二分搜尋法(Binary Search)，並研讀一下板上LOOKUP的精華帖

http://club.excelhome.net/thread-509072-1-1.html

http://club.excelhome.net/forum.php?mod=redirect&goto=findpost&ptid=113915&pid=1566407

1.二分搜尋法是一種演算法(Algorithm)，是lookup的計算機制，跟查找的數無關，lookup的第一個參數不管是什麼，都還是使用(非嚴格義意上的)二分搜尋法，也不會因為第一個參數為零，就變成「0分搜尋法」

2.二分搜尋法基本上是從中間開始找，你這種從前到後的找法，基本上是精確查找的作法(當然精確找法會遍歷，若全部都找不到則反回#N/A

3.亂序時，查找的流程比較複雜，跟你講的也有所不同，建議詳讀一下上面連結中的流程圖

以你提供的例子來說(本身是亂序的，是由{0;0;-0.2;-0.22;n-4個錯誤值}組成的序列

套進流程圖的話，查找的過程會是：

-----------------------    5、6的情形

left=1,right=5,posi=3

left=4

posi=4

left=5

posi=5

posi=4

-----------------------------------

7的情形

left=1,right=7,posi=4

left=5

posi=6

right=5

posi=5

posi=4

------------------------------------

8的情形

left=1,right=8,posi=4

left=5

posi=6→posi=7→posi=8

right=7

posi=6→posi=7

right=6

posi=5→posi=6

right=5

posi=5

posi=4

---------------------------------------------------

9(以上)的情形

left=1,right=9,posi=5

posi=6→posi=7→posi=8→posi=9

right=8

posi=4

left=5

posi=6→posi=7→posi=8

right=7

posi=6→posi=7

right=6

posi=5→posi=6

right=5

posi=5

posi=4

------------------------------------------------------

由此可以解釋為什麼會返回0.22

但是如果這個圖是對的，照理來說全部都會返回0.22，不應該出現0

由此可知，該流程圖在處理錯誤值上面，似乎仍然不完備

不知為何，POSI最後跑到2去了，這個值得好好研究

不過大體上來講，在不存在錯誤值的情況下，該流程圖應該是正確的

Bodhidharma

jsxjd 发表于 2013-8-11 10:37
楼主可能没注意到，
楼主的示例公式为：=LOOKUP(2,-1/LEFT(A16,ROW($1:19)),LEFT(A16,ROW($1:19)))
其 ...

以這個例子來說，由於不存在錯誤值，LOOKUP的流程圖的解釋完全ok

=LOOKUP(2,{1,3,5,2,6})

left=1,right=5,posi=3

right=2

posi=1

left=2

posi=2

posi=1

返回A(1)，即1

這個例子可以很明顯的看出，為何非升序的情況下，lookup會出問題：因為2<5，所以LOOK依二分搜尋法，自然只會對5左邊的值(right=2)進行查找
雖然posi4有想要找的值，但是lookup跟本不會去理它

=LOOKUP(2,{4,2,5,6})

left=1,right=4,posi=2

返回A(2)，即2

jsxjd

Bodhidharma 发表于 2013-8-11 12:51
以這個例子來說，由於不存在錯誤值，LOOKUP的流程圖的解釋完全ok
這個例子可以很明顯的看出，為何非 ...

图示是二分法的一般算法，但Lookup是否完全遵循？特殊情况又是怎么处理的？毕竟是一种猜测。没有发现例外，不等于完全如此。等发现问题为时晚矣。
最好能有LookUp 的源代码，这样一切都明白了。

Bodhidharma

jsxjd 发表于 2013-8-11 13:14
图示是二分法的一般算法，但Lookup是否完全遵循？特殊情况又是怎么处理的？毕竟是一种猜测。没有发现例外 ...

這個是http://club.excelhome.net/thread-113915-1-1.html中
大家集思廣益出來的東西
當然不保證正確，比方說在錯誤值的部分，樓主似乎就打破了這個猜想
不過在不存在錯誤值的時候，我覺得這個流程應該是沒問題的(至少到目前為止還沒有反例)
當然如果有源碼的話一切就簡單，但是微軟就沒有提供啊(菸)

jsxjd

Bodhidharma 发表于 2013-8-11 13:21
這個是http://club.excelhome.net/thread-113915-1-1.html中
大家集思廣益出來的東西
當然不保證正確， ...

哈哈，并不是为了否定这种猜测。要求升序排序，就是为了“二分法”实现提高效率，但是“二分法”会有好多细节问题。在不知道细节的情况下，不能“盲信”那个“流程图”。
我并不是说那张图不对，但我在不知道细节的情况下不可能说那张图“完全正确”，我现在只能说“正常情况下可以参考那张图”。

Bodhidharma

jsxjd 发表于 2013-8-11 13:43
哈哈，并不是为了否定这种猜测。要求升序排序，就是为了“二分法”实现提高效率，但是“二分法”会有好多 ...

嗯我完全同意啊…歸納法本來就有其侷限性，只能當經驗法則，而非嚴謹的證明
在被否證之前，只是假設它暫時成立，不代表這就是真理(Karl Popper的講法)
當確實被否證的時候，就要找新的解釋了…
(雖然我不完全認同Popper，但是在個情形還算適用啦…)
目前在處理錯誤值的部分已經被樓主否證，至於一般數字的部分，還沒有被否證
就加減拿來用吧，至少目前這玩意兒的解釋力還算ok~

dengjq2000

LOOKUP、VLOKKUP、HLOOKUP三个函数，这所以LOOKUP排行老大，足矣说明它的威慑力。
你这个问题主要是LOOKUP函数的二分法的原因。

上个月在回复一个主题时，也碰到同样的问题，对LOOKUP进行了系统搜索一下，不知道我这样分析是否能帮助你（具体见工作表：“笑笑_分析”）？

dengjq2000

张雄友 发表于 2013-8-11 08:39
我想问你一个问题：电脑4523.50元，用LOOKUP 怎么提取出来？

4523.50  这个数字。

=-LOOKUP(,-(0&MIDB(A1,SEARCHB("?",A1&0),ROW($1:18))))

张雄友

dengjq2000 发表于 2013-8-11 14:27
=-LOOKUP(,-(0&MIDB(A1,SEARCHB("?",A1&0),ROW($1:18))))

提取多重数值的呢？有通过的公式吗？可以向右拖的？