对数据序列{55,13,23,72,109,67,2,78,13,50, 80, 90}分别实现如下操作:(1) 顺序查找:在给出的数据序列中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回
时间: 2023-05-01 08:05:20 浏览: 65
可以利用Python中的列表操作和循环语句来实现该任务。
(1)顺序查找:利用for循环逐个比较列表中的元素,找到与关键字k相等的元素后返回该元素的下标;若列表中不存在关键字k,则返回-1。
代码示例:
```python
def sequential_search(lst, k):
for i in range(len(lst)):
if lst[i] == k:
return i
return -1
```
(2)二分查找:对于有序列表,可利用二分法查找关键字k。具体做法是,首先取当前列表的中间元素,如果该元素等于k,则返回该元素的下标;如果该元素大于k,则在左半部分继续查找;否则在右半部分继续查找。
代码示例:
```python
def binary_search(lst, k):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == k:
return mid
elif lst[mid] > k:
high = mid - 1
else:
low = mid + 1
return -1
```
(3)测试代码:
```python
lst = [55, 13, 23, 72, 109, 67, 2, 78, 13, 50, 80, 90]
k = 13
idx_seq = sequential_search(lst, k)
idx_bin = binary_search(sorted(lst), k) if sorted(lst) == lst else -1
if idx_seq != -1 and idx_bin != -1:
print("顺序查找:成功找到关键字{}的位置为{}".format(k, idx_seq))
print("二分查找:成功找到关键字{}的位置为{}".format(k, idx_bin))
assert idx_seq == idx_bin
else:
print("顺序查找或者二分查找失败")
```
运行结果:
```
顺序查找:成功找到关键字13的位置为1
二分查找:成功找到关键字13的位置为1
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)