《对分查找算法和解题思路》
该文是关于查找算法类电大毕业论文范文和算法方面硕士论文开题报告范文.
摘 要：对分查找是一种效率很高的查找方法,是浙教版《算法与程序设计》的重点内容之一.学生容易入门,但很难熟练应用.本文通过对对分查找算法的分析,探讨解题的一般策略,增强学生灵活应变的能力.
关键词：对分查找;核心代码;思路;规律
一、对分查找算法的特点
对分查找从字面上看有对分二字,大意就是每次查找,数据规模减半,一般情况下比顺序查找快很多,查询效率也较高.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
Ifa（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<R
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）.
上文结束语,此文是关于算法方面的查找算法论文题目、论文提纲、查找算法论文开题报告、文献综述、参考文献的相关大学硕士和本科毕业论文.
查找算法引用文献:
[1] 查找算法论文范例 查找算法论文范文例文2万字
[2] 查找重复率算法
[3] 优秀计算机算法分析论文题目 计算机算法分析论文标题怎么定
