用python实现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 12:05:54 浏览: 87
好的,我可以帮你解答这个问题。
首先,我们可以将给定的无序序列存储在一个列表中:
```python
lst = [1, 3, 4, 334, 67, 8, 13, 25, 3923, 10, 41, 5, 66, 52, 21, 64, 76, 658, 789, 546, 23, 56, 90, 109143, 178, 967, 11, 19]
```
接下来,我们可以实现顺序查找和折半查找算法。顺序查找算法比较简单,只需要从列表的第一个元素开始,逐个比较每个元素,直到找到与关键字相同的元素或者遍历完整个列表。折半查找算法则需要先将列表排序,然后从中间位置开始比较,如果中间元素大于关键字,则在左半部分继续查找,否则在右半部分继续查找,直到找到与关键字相同的元素或者左右部分都没有找到为止。
下面是顺序查找和折半查找算法的实现:
```python
def sequential_search(lst, key):
count = 0
for i, val in enumerate(lst):
count += 1
if val == key:
return i+1, count
return "No"
def binary_search(lst, key):
lst.sort()
low, high = 0, len(lst)-1
count = 0
while low <= high:
mid = (low + high) // 2
count += 1
if lst[mid] == key:
return mid+1, count
elif lst[mid] > key:
high = mid - 1
else:
low = mid + 1
return "No"
```
顺序查找算法的时间复杂度为O(n),而折半查找算法的时间复杂度为O(logn)。
最后,我们可以测试一下这两个算法:
```python
key = 13
print("顺序查找:", sequential_search(lst, key))
print("折半查找:", binary_search(lst, key))
key = 100
print("顺序查找:", sequential_search(lst, key))
print("折半查找:", binary_search(lst, key))
```
输出结果为:
```
顺序查找: (7, 7)
折半查找: (7, 3)
顺序查找: No
折半查找: No
```
可以看到,顺序查找和折半查找算法都能正确地找到与关键字相同的元素,并输出了需要进行的比较次数。
阅读全文