LOOKUP精确查找重复"0"值时的规律?

人贵于自省

tshaer 发表于 2013-10-9 09:16
看帖子有点糊涂了..
现在对于当二分法进行到最后时  能否用个简单的例子说明一下?
比如这个例子:

此时正好符合如果在第二个参数中找不到查找等于值lookup_value，则返回比它小的最大数值；http://club.excelhome.net/thread-807304-1-1.html，楼主再看看这个帖子

Bodhidharma

tshaer 发表于 2013-10-9 09:16
看帖子有点糊涂了..
现在对于当二分法进行到最后时  能否用个简单的例子说明一下?
比如这个例子:

依據流程圖，lookup(3,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3
posi=int((1+3)/2)=2
A(posi)=1<3=X，往右
2=posi<right=3，往上
left=posi+1=3
posi=int((3+3)/2)=3
A(posi)=7>3=X，往左
posi=left=3，posi不大於left，往下
posi=3，posi不等於1，再往下
posi=posi-1=2
返回A(posi)=A(2)，對應到的就是b

依據流程圖，如果是lookup(1,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3,posi=2
1=X=A(posi)=A(2)=1，往下
posi=2<right=3，往下
A(posi+1)=A(3)=7<>X=1
故直接返回A(posi)=A(2)，對應到b

Bodhidharma

人贵于自省 发表于 2013-10-9 09:58
此时正好符合如果在第二个参数中找不到查找等于值lookup_value，则返回比它小的最大数值；http://club.ex ...

感謝提供
[分享] 菜鸟的LOOKUP查找之二分法顿悟
這篇我之前倒是沒看過，對於一般情形這篇是比較口語話的解釋，可以搭配下篇學習：
[原创] LOOKUP二分法查找策略图文详解

不過上面兩篇是比較簡單的情形，當比較包含錯誤值，比較完整的說明，還是要回到我一開始提供的兩篇(相對之下比較不好讀)
[原创] 【公式解析系列】之LOOKUP(2,1/(条件),查找数组或区域)
[函数用法讨论系列10] LOOKUP的查找策略！

至於笑着...两年过去的那篇
[讨论] 奇怪的发现lookup 0分法的规率(学习与讨论)
我比較建議概念比較清楚後再讀，不然容易被誤導…那篇指出了lookup中關於錯誤值，流程圖中無法解釋的現象

tshaer

Bodhidharma 发表于 2013-10-9 12:43
依據流程圖，lookup(3,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3
posi=int((1+3)/2)=2

谢谢前辈不厌其烦的帮助!
lookup这个比较的过程还真是复杂,还在慢慢思考
再次衷心感谢!~

tshaer

Bodhidharma 发表于 2013-10-9 12:43
依據流程圖，lookup(3,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3
posi=int((1+3)/2)=2

对着流程图,用最简单的
=lookup(3,{2;1},{"a";"b"})="b"
=lookup(3,{2;4},{"a";"b"})="a"
终于把lookup流程图查找到区域边缘时的运作机制搞清楚了,  ——其实只要按lookup一直把查找的区域看做是升序排列的话, 一切就好解释了~

tshaer

Bodhidharma 发表于 2013-10-9 12:43
依據流程圖，lookup(3,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3
posi=int((1+3)/2)=2

依據流程圖，lookup(3,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3
posi=int((1+3)/2)=2
A(posi)=1<3=X，往右
2=posi<right=3，往上
left=posi+1=3
posi=int((3+3)/2)=3
A(posi)=7>3=X，往左
posi=left=3，posi不大於left，往下        先前对于流程图中判断posi>left不解,现在知道了是为了判断是否是抵达区域边缘,如果posi=left则告诉函数查找已到达最右侧, 即查找区域的最大值(尽管实际上并非最大值),而X比"最大值"小,那么又因为比"最大值"小一号的值比X小, 所以LOOKUP即认为这个小一号的值即为所查找的小于X的最大值,即A(posi-1)          不知是否可以这样理解?
posi=3，posi不等於1，再往下
posi=posi-1=2
返回A(posi)=A(2)，對應到的就是b

依據流程圖，如果是lookup(1,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3,posi=2
1=X=A(posi)=A(2)=1，往下
posi=2<right=3，往下
A(posi+1)=A(3)=7<>X=1
故直接返回A(posi)=A(2)，對應到b

Bodhidharma

tshaer 发表于 2013-10-10 22:55
依據流程圖，lookup(3,{1,1,7},{"a","b","c"})會這樣跑：
left=1,right=3
posi=int((1+3)/2)=2

唔…理解不太對

的確，要理解lookup二分法的流程圖
很重要的概念就是要知道lookup預設數據是升序的
第二參數的量太少的話不好說明，以下舉個例子：
lookup(7,{2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38})
首先left=1,right=19，要將left和right理解為「待查找的數據範圍」
left是最小，right是最大
然後lookup從中間(int(left+right)/2))開始找，posi=10
A(10)=20，比7還大，因此lookup就知道，大於等於10的posi都是比7還大，因此就不用再找了
因此right變成9，也就是只從{2,4,6,8,10,12,14,16,18}這組數據中找
再從中間找，posi=int((1+9)/2)=5，A(posi)=10
還是大於7，因此right就變成4，也就是只從{2,4,6,8}這組數是中找
可以看出來，lookup都是從中間找，一次就可以砍掉一半不需要再找的數據
因此叫做「二分搜尋法」，是一種相當有效率的查找方法
接下來posi=int((1+4)/2)=2，A(posi)=4，比7小
此時left變成3，也就是說比posi(3)小的數據都不需要找了(因為都比7小)
因此就只從{6,8}這組數據中找
再來posi=int((3+4)/2)=3，A(posi)=6，比7小
因此left變成4，再來posi=int((4+4)/2)=4，A(posi)=8，比7大
此時posi=left，也就是說，7已經比查找數據的最小值還要小了
因此若posi=1，就返回#N/A(因為第一參數比所有數據小)
不然的話posi=posi-1，變成3，也就是說返回比最小的數據「再小一點的數」
因此最後就返回A(3)=6

tshaer

Bodhidharma 发表于 2013-10-11 00:18
唔…理解不太對

的確，要理解lookup二分法的流程圖

因此就只從{6,8}這組數據中找
再來posi=int((3+4)/2)=3，A(posi)=6，比7小
因此left變成4，再來posi=int((4+4)/2)=4，A(posi)=8，比7大
此時posi=left，也就是說，7已經比查找數據的最小值還要小了
因此若posi=1，就返回#N/A(因為第一參數比所有數據小)
不然的話posi=posi-1，變成3，也就是說返回比最小的數據「再小一點的數」
因此最後就返回A(3)=6



可是能保证这个再小一点的数是小于X的吗?

Bodhidharma

tshaer 发表于 2013-10-11 09:04
因此就只從{6,8}這組數據中找
再來posi=int((3+4)/2)=3，A(posi)=6，比7小
因 ...

可以啊，除非left=1
不然left之所以會變成不是1的數，一定是因為left-1有和X比較過，也就是left-1<X因此不管是升序或亂序，這個都是可以保證的(只有left-1可以保證，其它在亂序情況下就不行了)

骑蚂蚁游江南

Bodhidharma 发表于 2013-10-11 20:27
可以啊，除非left=1
不然left之所以會變成不是1的數，一定是因為left-1有和X比較過，也就是left-1

好吧。二分法。真的好复杂。