浅析对分查找算法与解题思路

胡锋

摘 要：对分查找是一种效率很高的查找方法，是浙教版《算法与程序设计》的重点内容之一。学生容易入门，但很难熟练应用。本文通过对对分查找算法的分析，探讨解题的一般策略，增强学生灵活应变的能力。

关键词：对分查找;核心代码;思路;规律

一、对分查找算法的特点

对分查找从字面上看有对分二字，大意就是每次查找，数据规模减半，一般情况下比顺序查找快很多，查询效率也较高。N个元素，采用顺序查找算法，最坏的情况是查找N次，而采用对分查找算法，最坏的情况是查找Int（log2N+1）。显然当数据规模较大时，对分查找效率远胜顺序查找。对分查找虽然速度快，但对数据有要求，不能杂乱无序，必须是升序或降序排列，或者是按照某种规则有序排列的。

二、对分查找算法的核心代码

对分查找既然要对分，就必须指定对分点，即中点位置，假设L为左端点位置，R为右端点位置，M为中点位置。中点M的表示方法有很多，不同方法也不尽相同。常见为M=（L+R）＼2， M=（L+R+1）＼2，这两种方法的主要区别是当数据个数是偶数时，中间位置是两个数，前者取左边一个，后者取右边一个。假设现有数组A中有N个数据并升序排列，查找key所在的位置。如果中间位置M的数A（M）等于key，则M就是结果;如果中间位置M的数A（M）大于key，则说明key只能到M之前去寻找（因为后面的数更大）;如果中间位置M的数A（M）小于key，则说明key只能到M之后去寻找（因为前面的数更小）。 重复上面的过程，直到找到数据或找完数据。

将上述文字描述变为VB核心代码，如下：

L=1  ：      R=N

Do While L<=R  ‘L<=R表示还有数据，至少1个数据

M=（L+R） ＼ 2

If    a（M）=key  Then

Exit Do    ‘找到key后退出

ElseIf  a（M）>key Then

R=M-1    ‘中间位置的数太大了，到M之前去找

Else

L=M+1   ‘中间位置的数太小了，到M之后去找

End If

Loop

上述代码运行结束后，如何判断是否找到key？

要弄清楚这个问题，首先我们知道该算法主体是一个循环结构，结束循环的方式有两个。其一，L>R，使得Do While语句循环条件不成立;其二，找到key，通过Exit Do语句，强制结束循环。显然这两个方式不可能同时起作用，因此找到key时必定强制退出，此时依然L<=R，而没有找到key时，必定是L>R来结束循环。

我们可以通过以下方式来判断找到key了：

1 L<=R      （此时必定是强制退出循环）

2 A（M）=key  （这是强制退出循环的前提条件）

3 flag=True （设置标记，初始为False，找到时设为True）

引入标记的核心代码如下：

L=1  ：   R=N   ：    flag=False

Do  While L<=R  And Not flag

M=（L+R） ＼ 2

If  a（M）=key  Then

flag=True

ElseIf  a（M）>key Then

R=M-1

Else

L=M+1

End If

Loop

最后只要判斷flag即可知道是否找到Key，代码可读性高。

熟练掌握核心代码是解题的基础，也是突破各种对分查找变式的关键所在。

三、各种对分查找变式常用解题思路

边界搜索问题，比如在有序数据中查找重复数据key的第一个或最后一个位置;又如找一个小于key的最大值或大于key的最小值。

虽然这类问题都可以利用核心代码找到等于key的位置，然后按顺序向前或向后依次搜寻来解决。但这部分就变成顺序查找了，失去了对分查找的效率。因此优先考虑使用对分查找来解决问题。

举例：

从表格中可以看出位置4至9都是6。

查找第1个6的位置是4，最后一个6的位置是9 。

查找小于6的最大值的位置是3，大于6的最小值的位置是10。

从本质上来看都是搜索边界，一个内边界，一个外边界。

核心代码用来解决这类问题时，必定需要进行适当改变。中间值太小或太大的处理方式没什么不同，主要不同在于核心代码中找到key就退出了，而在边界搜索时，找到key时问题还没有求解，故不能结束。本例中，假定中间位置采用M=（L+R）＼2，则第一次找到位置是6，显然6不是问题的解。

我们以找第一个等于6的位置为例，当中间值等于6时，可能前面还有6，因此应该继续向前寻找。

查找第一次出现key的位置（假定数据为升序），参考代码如下：

L=1  ：   R=n

Do  While L

m=（L+R） ＼ 2

If  a（m）< key  Then ‘注意这里判断中间值太小的情况

L=m+1

Else              ‘中间值太大和相等时都继续向前找

R=m-1

End If

Loop

如果key值在序列中，则L就是第1个出现的位置，而R就是这第一个数之前的位置（换句话来说，就是比key小的最大值的位置，当然如果R=0了，说明位置R实际不存在，即序列中没有数比key小）。如果key值不在序列中，L和R又表示什么呢（此时L=R+1，循环结束条件）？如果L和R都存在（1～n），那么L表示第一个比key大的数的位置，R表示最后一个比key小的数的位置，即如果key要插入到序列中使序列依然有序，那么key只能放在位置R与L之间;如果位置L不存在（此时R=n，L=n+1），说明key大于序列中所有数;如果位置R不存在（此时L=1，R=0），说明key小于序列中所有数。

从上面的分析可以发现找一个小于key的最大值位置的代码基本一致，只是前者用L，后者用R。

四、对分查找算法的规律

一般情况下，判断对分查找是向前还是向后查找并不是特别难，难的是相等时该向前还是向后查找，以及调整端点位置时该调整到哪里。通过前面的分析，我们可以得出以下规律：如果要找第一次出现的位置，相等时继续向前查找;如果要找最后一次出现的位置，相等时继续向后查找。至于位置变化时，是否要加减一，关键看中间点是否是可能的解，如果是则保留，反之则加减一。

五、结语

对分查找是一种效率很高的查找方法，在实际生活中应用很广，也是信息技术选考中的一个高频考点，有一定的难度。要熟练掌握对分查找算法，就要熟悉它的工作原理，熟识它的核心代码，善于分析问题，了解一般规律。对分查找虽然效率高，但前提是数据有序，这一点必须牢记。

参考文献

[1]曾伟锋.高中信息科技计算思维教学实践——以对分查找算法为例[J].中国信息技术教育，2018（Z2）.