給定无序序列{1,3,4,34, 67,8,13,25,39,23,10,41,33,66,52, 21, 64, 76, 58, 789, 545, 23, 56, 90, 109,143,178, 967, 11,19);一 2.查找与输入的给定关键宇相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为 1)和需要进行的比较次数,不存在则输出"No”,序列位序从1到口。 3.实现顺序查找和折半查找算法。
时间: 2023-10-25 07:09:51 浏览: 89
好的,那么我来帮您解答这个问题。
2. 对于给定的无序序列,如果要查找与给定关键字相同的元素,我们可以使用顺序查找算法来实现。顺序查找的基本思路是从序列的第一个元素开始逐个比较,直到找到相同的元素或者遍历完整个序列。具体实现可以参考下面的代码:
```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", count)
```
上述代码中,`seq` 表示要查找的序列,`key` 表示要查找的关键字。函数返回一个元组,第一个元素是找到的元素在序列中的位序,第二个元素是需要进行的比较次数。如果没有找到,则返回字符串"No"。
3. 实现顺序查找和折半查找算法。顺序查找的代码上面已经给出了,下面给出折半查找(二分查找)的代码。
```python
def binary_search(seq, key):
count = 0
left, right = 0, len(seq)-1
while left <= right:
count += 1
mid = (left + right) // 2
if seq[mid] == key:
return (mid+1, count)
elif seq[mid] < key:
left = mid + 1
else:
right = mid - 1
return ("No", count)
```
上述代码中,`seq` 表示要查找的序列,`key` 表示要查找的关键字。函数返回一个元组,第一个元素是找到的元素在序列中的位序,第二个元素是需要进行的比较次数。如果没有找到,则返回字符串"No"。
需要注意的是,折半查找算法要求序列是有序的,因此在使用该算法前,需要先将无序序列进行排序。
阅读全文