给定无序序列{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}现进行排序再查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的比较次数,不存在则输出"No",序列位序从1到n。 3.实现顺序查找和折半查找算法。
时间: 2023-10-24 19:08:42 浏览: 149
好的,这是一个排序和查找的问题。那么先回答第一个问题:给定无序序列{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},假设我们使用快速排序算法对其进行排序,则排序后的序列为:
{1, 3, 4, 8, 10, 11, 13, 19, 21, 23, 23, 25, 34, 39, 41, 52, 55, 56, 64, 66, 67, 68, 76, 90, 109, 143, 178, 546, 789, 967}
接下来,我们可以使用顺序查找和折半查找算法进行查找。
顺序查找算法:
顺序查找算法是一种简单直观的查找方法,它从序列的第一个元素开始,依次比较每个元素,直到找到目标元素或遍历完整个序列为止。对于无序序列和简单查找,顺序查找算法是最基本的查找方法。其时间复杂度为O(n)。
以下是顺序查找算法的python实现:
```python
def sequential_search(lst, key):
for i in range(len(lst)):
if lst[i] == key:
return i+1, i+1
return "No"
```
其中,lst表示要查找的序列,key表示要查找的关键字。函数返回值为元素的位序和比较次数。
折半查找算法:
折半查找算法是一种高效的查找方法,它适用于已排序的序列。折半查找算法每次将待查找区间缩小一半,直到找到目标元素或缩小到区间为空。其时间复杂度为O(log2n)。
以下是折半查找算法的python实现:
```python
def binary_search(lst, key):
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"
```
其中,lst表示要查找的序列,key表示要查找的关键字。函数返回值为元素的位序和比较次数。
接下来,如果你有关键字要查找,请告诉我关键字,我将使用上述算法进行查找。
阅读全文