[Visual Basic]二分查找
2024-10-08 21:47:13
模板
i=1:j=n 'i初值为1,j初值为n
Do while i<=j '当i<=j时,通过循环进行查找
m=fix((i+j)/2) '计算出中间元素的下标m
If d(m)=key Then '若中间元素d(m)和key相等,则输出m;退出循环
print m
Exit Do
End If
If d(m)<key Then
i=m+1 '[m+1,j]下一查找范围
Else
j=m-1 '[i,m-1]
End If
Loop
If i>j Then print"0" '未找到
注意点及变式
查找次数:LogN(若不是整数,则向上取整)
计算中间元素的下标的方法有很多种,是选择题中小小的坑(我掉进去好多次了)
'e.g.
'偶数组 1 2 3 4 5 6 7 8
'奇数组 1 2 3 4 5 6 7 8 9
'偶数组 i=1:j=8 奇数组 i=1;j=9
' 偶数组 奇数组 备注
① Int((i+j)/2) ' 4 4 删除小数部分而返回剩下的整数
② Fix((i+j)/2) ' 4 4
③ (i+j)/2 ' 4.5 5 Dim c as integer c=(i+j)/2=4
④ (i+j)\2 ' 4 5 选择左数或中间数
⑤ (i+j+1)/2 ' 5 5 选择右数或中间数
⑥ Fix((i+j)/2 +0.5)'
一般而言题目多为选择左数与中数。
还要看清数组编号是0开始还是1开始,在高中试卷里是1开始为多
二叉树法
qwq图片是从老师课件里白嫖来哒(溜
例题:
有如下VB程序段:
i = 1 : j = 10 : flag = True : n = 0
Key = Val(Text1.Text)
Do While i <= j And flag = True
m = (i + j) \ 2
If a(m) = Key Then
flag = False
Elseif a(m) > Key Then
i = m + 1 : n = n - 1
Else
j = m - 1 : n = n + 1
End If
Loop
数组元素a(1)到a(10)依次是99, 94, 90, 87, 70 , 69 , 60 , 56 , 45 , 36 ,变量n的值最终是0,则文本框Text1输入的数字可能是
A.100 B.87 C.69 D.4
用二叉树解题的最明显的特征就是n=n-1;n=n+1,在本题中前者的含义是“当需要查找的值Key比二分点要小,则向右查找,并且n-1”(数据是降序),后者反之亦然。
n=向左缩进的次数-向右缩进的次数
所以模拟出下面的一棵二叉树(蓝字为数,红字为n)
很容易看出n=0时,所查数为69、70、90.故题目的答案为C
以上是很基本的裸题,先来看看注意点:
- 数字排序升or降?什么时候n+1或是n-1?
- 查找到数时程序是否继续进行
本题中采用了Flag与If、ElseIf、Else,还有Exit For也能达到找到就会停止程序的目的。如果代码中缺少上面的语句,如两个If且不带Exit For、只有If与Else,程序继续,n的值仍然会改变,这时候就还要继续画二叉树了 - 选项中有大于最大值和小于最小值的数
就是题中的A100与D4,图中已画出。需要在原二叉树(仅数列)的最左侧与最右侧扩展开,具体见图。 - 变式:求n满足0时输入数据的范围
Answer:(Loading……)这块地方我也还不懂……如果你会的话可以来教教我吗……
暂时想到的难点就这些了,如果后面写题目又遇到新的,会继续更新。欢迎纠正哦~
小花絮:写博客时问老师题目的截图(肯定又是和lp过节去了哼这个男人略略略)
最新文章
- SQL Server SQL性能优化之--通过拆分SQL提高执行效率,以及性能高低背后的原因
- 接口测试之基于LoadRunner的一个简单示例
- 利用SPM工具运行自己创建的小组件(使用common-model向后台接口请求数据)
- 数据库mark
- iOS从健康app中获取步数信息
- 解决ubuntu下的文本编辑器gedit的乱码问题
- sqlserver 死锁查看辅助存储过程
- Java乔晓松-android的四大组件之一Service(服务的绑定)
- 大约Android 了解权限管理
- Java加密与解密笔记(四) 高级应用
- step_by_step_xUnit_Net_ABP
- 【NIFI】 Apache NiFI 集群搭建
- 53_并发编程-线程-GIL锁
- ES6+Vue+webpack项目,在ie11中请求后台接口后数据更新,但是页面没有刷新?
- 14 python读取文件时出现UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode byte 0xb7 in position 26: illegal multibyte sequence解决方法
- kvm虚拟化管理平台WebVirtMgr部署-完整记录(1)
- topcoder srm 320 div1
- Oracle跨库复制表结构
- selenium和appium启动的感悟
- HDFS 手写mapreduce单词计数框架