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

香川群子 · 发表于 2012-3-31 17:23

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

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

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

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

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

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

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

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

香川群子 · 发表于 2012-3-31 17:25

这个是具体的代码：

Function VL(x, r, Optional k = 0)
' Exit Function
m = r.Count: h = m + 1: l = 0: t = l + (h - l) \ 2: s = " |"
If IsNumeric(x) Then x = Val(x) Else x = x.Text
Do
If IsNumeric(r.Item(t)) Then y = Val(r.Item(t)) Else y = r.Item(t).Text
If x < y Then
s = s & "<" & y & "(" & t & ") " & ChrW(8594)
If t = 1 Then VL = 1: Exit Do
h = t: t = l + (h - l) \ 2
Else
If x = y Then
q = t: s = s & "=" & y & "(" & t & ") " & ChrW(8594)
For t = t + 1 To h - 1
If IsNumeric(r.Item(t)) Then y = Val(r.Item(t)) Else y = r.Item(t).Text
If x = y Then q = t Else Exit For
Next
VL = 2: Exit Do
End If
If t = h - 1 Then VL = 3: Exit Do
p = t: s = s & ">" & y & "(" & t & ") " & ChrW(8594)
l = t: t = l + (h - l) \ 2
End If
Loop
If k = 0 Then
If VL = 1 Then
VL = "#N/A"
ElseIf VL = 2 Then
VL = x
Else
VL = y
End If
ElseIf k = 1 Then
If VL = 1 Then
VL = "#N/A"
ElseIf VL = 2 Then
VL = q
Else
VL = t
End If
Else
If VL = 1 Then
VL = "NA (1)" & s & "S #NA|1"
ElseIf VL = 2 Then
VL = x & " (" & q & ")" & s & "=" & x & "(" & q & ")" & ChrW(8594) & "=|2"
ElseIf VL = 3 Then
VL = y & " (" & t & ")" & s & ">" & y & "(" & t & ")" & ChrW(8594) & ">H|3"
End If
End If
End Function

复制代码

李甲 · 发表于 2012-3-31 17:33

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

Zamyi · 发表于 2012-3-31 17:37

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

香川群子 · 发表于 2012-3-31 17:39

本帖最后由香川群子于 2012-3-31 17:41 编辑

核心代码解释：

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 · 发表于 2012-3-31 17:54

字典是哈希吧

香川群子 · 发表于 2012-4-5 23:12

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

renyucai1963 · 发表于 2012-4-6 09:25

{:soso_e163:}{:soso_e179:}

zxzyer2009 · 发表于 2012-5-4 18:11

想穿裙子老师真厉害！

彭希仁 · 发表于 2012-10-8 12:09

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

		自动登录	找回密码
密码			免费注册

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

评分

评分