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.查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的比较次数,不存在则输出"No",序列位序从1到n。 3.实现顺序查找和折半查找算法。
时间: 2023-10-17 15:05:11 浏览: 56
3-1 3-2 3-3 Algorithms.docx
好的,这是一个关于查找算法的问题。以下是顺序查找和折半查找算法的实现代码:
```python
# 顺序查找算法
def sequential_search(seq, key):
count = 0
for i in range(len(seq)):
count += 1
if seq[i] == key:
return i+1, count
return "No"
# 折半查找算法
def binary_search(seq, key):
count = 0
left = 0
right = len(seq) - 1
while left <= right:
count += 1
mid = (left + right) // 2
if seq[mid] == key:
return mid+1, count
elif seq[mid] > key:
right = mid - 1
else:
left = mid + 1
return "No"
```
这里顺序查找的时间复杂度为O(n),折半查找的时间复杂度为O(log n)。
阅读全文