(1) 建立一个数据为整数的顺序表。根据用户输入的查找值,实现顺序表的顺序查找。 (2) 建立一个有序的整数构成的顺序表,根据用户输入的查找值,实现二分查找,并输出比较的元素,提示是否查找成功。要求实现递归和非递归算法。
时间: 2024-03-16 07:44:03 浏览: 36
编写函数,建立一个顺序表并输出,计算该顺序表的长度。 实现在顺序表中查找第i个元素的值。实现在顺序表中第i个位置上插入值为x的
5星 · 资源好评率100%
好的,你的第一个问题是关于数据结构和算法的。我来回答你。
(1) 顺序查找
顺序查找又称线性查找,是一种简单直观的查找方法。基本思想是从表的一端开始,依次比较表中的每个元素,直到找到查找的元素或查找结束为止。
顺序查找的代码如下:
```python
def sequential_search(seq_list, target):
for i in range(len(seq_list)):
if seq_list[i] == target:
return i
return -1 # 如果没找到,返回 -1
```
(2) 二分查找
二分查找又称折半查找,是一种高效的查找方法。基本思想是将有序表分成两部分,取中间元素进行比较,如果相等,则查找成功;如果不相等,则根据比较结果确定继续查找的那一部分,直到查找成功或查找结束为止。
递归实现二分查找的代码如下:
```python
def binary_search_rec(seq_list, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if seq_list[mid] == target:
return mid
elif seq_list[mid] > target:
return binary_search_rec(seq_list, target, left, mid-1)
else:
return binary_search_rec(seq_list, target, mid+1, right)
```
非递归实现二分查找的代码如下:
```python
def binary_search(seq_list, target):
left = 0
right = len(seq_list) - 1
while left <= right:
mid = (left + right) // 2
if seq_list[mid] == target:
return mid
elif seq_list[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1 # 如果没找到,返回 -1
```
以上是关于顺序表的顺序查找和有序表的二分查找的实现方法,希望能够帮到你。
阅读全文