对Lookup二分法查找定位过程的模拟解析

香川群子

经常听说，Excel中的Lookup、VLookup，甚至于字典方法，

本质上都是靠二分法来进行快速查找定位的。

即，从中间位置取值作比较，如果>比较值则向后再取中间值、如果<比较值则向前再取中间值，
然后继续比较，直到找到相同值，或查询到最小/最大位置时结束。


因为有如此做法，所以当对象数据未经按从小到大的顺序排序时，
使用Lookup查询经常会返回一个令人一下子不知来历的位置的值。

总之，二分法虽然大家都听懂了，也相信了，
但具体是一个怎样的过程，一下子很难理解。


………………
附件中，我写了一段代码，模拟了二分法的查找过程。

使用自定义函数，可以返回每一查找步骤的比较值、查询位置，直到最后结束。

按此过程在来看，应该会更容易理解二分法的做法了。

香川群子

这个是具体的代码：

1. Function VL(x, r, Optional k = 0)
   
2. '    Exit Function
   
3.     m = r.Count:    h = m + 1:  l = 0:    t = l + (h - l) \ 2: s = " |"
   
4.     If IsNumeric(x) Then x = Val(x) Else x = x.Text
   
5.     Do
   
6.         If IsNumeric(r.Item(t)) Then y = Val(r.Item(t)) Else y = r.Item(t).Text
   
7.         
   
8.         If x < y Then
   
9.             s = s & "<" & y & "(" & t & ") " & ChrW(8594)
   
10.             If t = 1 Then VL = 1: Exit Do
    
11.             h = t:       t = l + (h - l) \ 2
    
12.         Else
    
13.             If x = y Then
    
14.                 q = t: s = s & "=" & y & "(" & t & ") " & ChrW(8594)
    
15.                 For t = t + 1 To h - 1
    
16.                     If IsNumeric(r.Item(t)) Then y = Val(r.Item(t)) Else y = r.Item(t).Text
    
17.                     If x = y Then q = t Else Exit For
    
18.                 Next
    
19.                 VL = 2: Exit Do
    
20.             End If
    
21.             If t = h - 1 Then VL = 3: Exit Do
    
22.             p = t: s = s & ">" & y & "(" & t & ") " & ChrW(8594)
    
23.             l = t: t = l + (h - l) \ 2
    
24.         End If
    
25.     Loop
    
26.    
    
27.     If k = 0 Then
    
28.         If VL = 1 Then
    
29.             VL = "#N/A"
    
30.         ElseIf VL = 2 Then
    
31.             VL = x
    
32.         Else
    
33.             VL = y
    
34.         End If
    
35.     ElseIf k = 1 Then
    
36.         If VL = 1 Then
    
37.             VL = "#N/A"
    
38.         ElseIf VL = 2 Then
    
39.             VL = q
    
40.         Else
    
41.             VL = t
    
42.         End If
    
43.     Else
    
44.         If VL = 1 Then
    
45.             VL = "NA (1)" & s & "S #NA|1"
    
46.         ElseIf VL = 2 Then
    
47.             VL = x & " (" & q & ")" & s & "=" & x & "(" & q & ")" & ChrW(8594) & "=|2"
    
48.         ElseIf VL = 3 Then
    
49.             VL = y & " (" & t & ")" & s & ">" & y & "(" & t & ")" & ChrW(8594) & ">H|3"
    
50.         End If
    
51.     End If
    
52. End Function
    

复制代码

李甲

研究……二分法让LOOKUP很给力

Zamyi

偶不同意这种说法，Lookup有精确查找和顺序查找，都是从指定位置到目标位置顺序查找的，找到第一个符合条件就退出。

香川群子

核心代码解释：

    m = r.Count '元素总数
   t = (m +1) \ 2 '第1步查询中间位置，如9或10个元数取5,11或12个元素取6
   
    '下面Do……Loop循环，x=检查值，y=当前比较值
    Do
        If x < y Then '如果小于比较值
            If t = 1 Then VL = "#N/A" : Exit Do '如果比第1个值还小，则返回找不到错误值。
            h = t:       t = l + (h - l) \ 2 '以当前位置为最高位置，计算向下查询的中间位置
        Else
            If x = y Then '如果已经和比较值相等了
                q = t '记录当前位置
                For t = t + 1 To h - 1 '向后遍历查询比对是否还有相同值
                    If x = y Then
                       q = t '如果还相同，则更新位置
                    Else
                       Exit For '如果不相同则直接退出
                    End If
                Next
                VL = q : Exit Do '返回最后一个相同值位置
            End If
            
           '以下为大于比较值时
            If t = h - 1 Then VL = t: Exit Do '如果当前查询位置和已检查最高位置只差一个时可结束检查了。
            p = t '否则记录当前位置
            l = t: t = l + (h - l) \ 2 '计算向后查询的新的中间位置
        End If
    Loop
   

上面是主要代码过程，具体的一些细节代码，就忽略掉了。

liucqa

字典是哈希吧

香川群子

经典12球中有一重量不等坏球的问题。

renyucai1963

{:soso_e163:}{:soso_e179:}

zxzyer2009

想穿裙子老师真厉害！

彭希仁

LOOKUP用的一定不是哈希表,因为一个函数建一次哈希表很不值,
只要数据是排序好的,使用二分法并不会比哈希表慢.