.给定无序序列{1,3,4,34,67,8,13,25,39,23,10,41,55,66,52,21,64,76,68,789,546,23,56,90,109,143,178,967,11,19}; 2.查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的比较次数,不存在则输出"No",序列位序从1到n。 3.实现顺序查找和折半查找算法。
时间: 2023-10-17 09:05:11 浏览: 47
好的,我知道了你的问题。以下是我的回答:
1. 无序序列为:{1,3,4,34,67,8,13,25,39,23,10,41,55,66,52,21,64,76,68,789,546,23,56,90,109,143,178,967,11,19}
2. 顺序查找算法:
输入关键字:23
顺序查找结果:元素23位于序列的第10位,进行了10次比较
输入关键字:100
顺序查找结果:No
折半查找算法:
输入关键字:23
折半查找结果:元素23位于序列的第10位,进行了3次比较
输入关键字:100
折半查找结果:No
3. 顺序查找算法的实现:
```
def sequential_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i+1, i+1
return "No"
lst = [1, 3, 4, 34, 67, 8, 13, 25, 39, 23, 10, 41, 55, 66, 52, 21, 64, 76, 68, 789, 546, 23, 56, 90, 109, 143, 178, 967, 11, 19]
key = 23
print("输入关键字:", key)
result = sequential_search(lst, key)
print("顺序查找结果:", result[0], "位于序列的第", result[1], "位,进行了", result[1], "次比较")
key = 100
print("输入关键字:", key)
result = sequential_search(lst, key)
print("顺序查找结果:", result)
```
4. 折半查找算法的实现:
```
def binary_search(lst, key):
left, right = 0, len(lst)-1
count = 0
while left <= right:
mid = (left+right) // 2
if lst[mid] == key:
return mid+1, count+1
elif lst[mid] > key:
right = mid - 1
else:
left = mid + 1
count += 1
return "No"
lst = [1, 3, 4, 34, 67, 8, 13, 25, 39, 23, 10, 41, 55, 66, 52, 21, 64, 76, 68, 789, 546, 23, 56, 90, 109, 143, 178, 967, 11, 19]
lst.sort() # 折半查找前要先将序列排序
key = 23
print("输入关键字:", key)
result = binary_search(lst, key)
print("折半查找结果:", result[0], "位于序列的第", result[1], "位,进行了", result[1], "次比较")
key = 100
print("输入关键字:", key)
result = binary_search(lst, key)
print("折半查找结果:", result)
```