基础扩展 | 12. 二分查找算法

学习Excel技术，关注微信公众号：

excelperfect

我家小孩特别喜欢玩游戏，一有空就缠着我和她妈与她一起玩游戏。有一次，吃完晚饭后，她又缠着我要玩游戏，而我又想抓紧时间快点将第二天的微信公众号文章搞出来。灵机一动，我对她说，我们现在玩一个猜数字的游戏，如果我连续3次都能猜中你心里想的数字，那你就自已玩去。她一听就答应了。

规则是这样的，她先想1至100中的任意一个数字，我最多只猜7次，就能猜中她心里想的数字，但她要在我说出数字之后与她心中的数字进行比较并回答是小了还是大了。如下图1所示，她心里想的数字以及我猜的次数。

图1

这是为什么？

哈哈！“骗”小孩可以，明眼人一看就知道了其中的玄机，我用的是二分查找法。每次都能排除一半的数字，对于100个数字，找到想要的数字绝对不会超过7次。就拿猜数字67来说，我第一次说1-100中间的数字50，她说小了；然后我又猜50-100中间的数字75，她说大了；我接着猜50-75中间的数字62，她说小了；……，依此类推，最后在第7次猜中结果。对于猜中数字35，只用了6次。

此外，还应注意到，我们查找的数字都是已经按顺序排好了的，也就是说，是一组有序的数字。

以上就是二分查找算法的基本原理。如何转换为程序呢？

我们以low和high分别代表数组中要查找范围的下界和上界，以middle表示查找范围的中间位置。假设我们要在[9,13,15,27,36,49,52,68,72,80,90]中查找数值68，下图2描述了具体的查找过程。

图2

最后找到68位于下标7的位置，也就是数组的第8个元素。

由以上原理，可以编写实现二分查找的VBA代码：

'passArray代表传递给函数的数组

'FindNum代表要查找的数值

Function BinarySearch(passArray() As Long, FindNum As Long) As Long

'声明变量

'分别代表数组下标

Dim low As Long

Dim high As Long

Dim middle As Long

'左侧下标

low = LBound(passArray)

'右侧下标

high = UBound(passArray)

Do While (low <= high)

'中间下标

middle = (low + high) \ 2

'如果中间元素为要找的数值,则返回

If FindNum = passArray(middle) Then

BinarySearch = middle

Exit Function

'如果查找的数值比中间元素小

'则修改右侧下标

ElseIf FindNum < passArray(middle)Then

high = middle - 1

'如果查找的数值比中间元素大

'则修改左侧下标

Else

low = middle + 1

End If

Loop

'没有找到返回-1

BinarySearch = -1

End Function

使用上图2中的示例数组来测试BinarySearch函数，代码如下：

Sub test()

Dim result As Long

Dim myArray(10) As Long

Dim num As Long

myArray(0) = 9

myArray(1) = 13

myArray(2) = 15

myArray(3) = 27

myArray(4) = 36

myArray(5) = 49

myArray(6) = 52

myArray(7) = 68

myArray(8) = 72

myArray(9) = 80

myArray(10) = 90

num = 68

result = BinarySearch(myArray, num) + 1

If result <> -1 Then

MsgBox "数组中第 " & result & " 个数字是" & num

Else

MsgBox "数组中找不到数字" & num

End If

End Sub

运行后的结果如下图3所示。

图3

下面为二分查找算法的VBA代码图片版：