编写一个程序,分别用顺序查找和折半查找实现对线性表中数据元素的查找(假设线性表中的元素都是int型)。主程序输入数据元素的值
时间: 2024-05-03 09:17:18 浏览: 10
顺序查找:
```python
def sequential_search(lst, x):
for i in range(len(lst)):
if lst[i] == x:
return i
return -1
```
折半查找:
```python
def binary_search(lst, x):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == x:
return mid
elif lst[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
```
其中,`lst`为要查找的线性表,`x`为要查找的元素值。如果查找成功,返回该元素在线性表中的下标;否则返回-1。
主程序:
```python
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
x = int(input("请输入要查找的元素值:"))
index1 = sequential_search(lst, x)
if index1 != -1:
print("顺序查找:元素值为%d的元素在线性表中的下标为%d" % (x, index1))
else:
print("顺序查找:元素值为%d的元素不在线性表中" % x)
lst.sort()
index2 = binary_search(lst, x)
if index2 != -1:
print("折半查找:元素值为%d的元素在线性表中的下标为%d" % (x, index2))
else:
print("折半查找:元素值为%d的元素不在线性表中" % x)
```
其中,先使用顺序查找,再将线性表排序后使用折半查找。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)