查找算法 练习-2021届高三信息技术复习(无答案)
查找算法及程序实现
一、顺序查找
- 基本思想
在一组数据中按照顺序查找某一个关键字。
- 核心代码1(For语句)
key = Val(Text1.Text)
For i = 1 To n
c = c + 1 '查找次数加1
If a(i) = key Then
Text2.Text = "在数组的" + Str(i) + "位置中"
Exit For '退出For语句
End If
Next i
If i = n+1 Then '写成If i >n Then也可以
Text2.Text = "在数组中没有找到" + Str(key)
End If
Text3.Text = "共查找了" + Str(c) + "次"
- 核心代码2(Do语句)
key = Val(Text1.Text)
i = 1:c=0:flag = false
Do While i <= n and flag = false
c = c + 1 '查找次数加1
If a(i) = key Then
Text2.Text = "在数组的" + Str(i) + "位置中"
flag = true '标记找到目标
End If
i = i + 1
Loop
If flag = false Then '写成If i >n and flag = false Then也可以
Text2.Text = "在数组中没有找到" + Str(key)
End If
Text3.Text = "共查找了" + Str(c) + "次"
二、对分查找
- 基本思想
对分查找算法先把待查找的数据进行排序,然后按照折半思想进行查找。假设待查找数据按升序排列,将数组中间位置元素与查找关键字key比较,如果相等,则查找成功;否则利用中间位置将数组分成前、后两个子数组,如果查找关键字key大于中间位置元素,则进一步查找后一半子数组,否则进一步查找前一半子数组。重复以上过程,直到找到key,或直到子数组不存在为止,此时查找不成功。
- 核心代码(数组已升序排列)
key=val(Text1.text)
i = 1: j = n:c=0 'i表示起始边界,j表示终止边界
Do While i <= j '查找区间至少包含一个元素
m = (i + j) \ 2 '取中间位置,有多种写法,如:m=fix((i+j)/2)或m=int((i+j)/2)
c=c+1
If a(m) = key Then
Text2.Text = Str(m)
Exit do '退出Do语句
End If
If key < a(m) Then '或
j = m – 1 '前半段找
Else
i = m + 1 '后半段找
End If
Loop
If i>j then Text2.Text ="找不到" '查找的区间为空
Text3.Text = "共查找了" + Str(c) + "次"
- 对分查找算法变式(顺序查找类似)
key=val(Text1.text)
i = 1: j = n:c=0:found=False 'found=False表示还未找到
Do While i <= j and found=False 'found=False也可以写成not found
m = (i + j) \ 2 '取中间位置
c=c+1