查找算法的实现要求如下1.给定无序序列1,3,4,334, 67,8, 13,25, 3923,10,41," 5,66,52,21,64,76,658, 789,546,23,56,90,109143, 17 8, 967, 11,19); 2.查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存 在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的 比较次数,不存在则输出"No",序列位序从1到n。 3.实现顺序查找和折半查找算法。
时间: 2023-08-22 18:05:54 浏览: 79
查找和排序算法的实现 (实验七).pdf
以下是顺序查找和折半查找算法的Python代码实现:
```python
# 顺序查找算法
def sequential_search(lst, key):
count = 0 # 记录比较次数
for i in range(len(lst)):
count += 1
if lst[i] == key:
return i+1, count
return "No", count
# 折半查找算法
def binary_search(lst, key):
count = 0 # 记录比较次数
low, high = 0, len(lst)-1
while low <= high:
count += 1
mid = (low + high) // 2
if key < lst[mid]:
high = mid - 1
elif key > lst[mid]:
low = mid + 1
else:
return mid+1, count
return "No", count
```
其中,`lst`为给定无序序列,`key`为需要查找的关键字。`sequential_search`函数实现顺序查找算法,`binary_search`函数实现折半查找算法。函数会返回找到的元素在序列中的位序和比较次数,若未找到则返回"No"。
阅读全文