(1)基于顺序查找表实现顺序查找和二分查找算法;(2)使用两个不同大小的查找表进行两次理论和实际性能对比;(3)根据实验环境调整两次查浅表的大小,使得: 第1次查找表的长度—[第2次查找表长度/10];第2次顺序查找的时间介于[9000,9999]ms之间。代码示例
时间: 2024-02-17 22:02:53 浏览: 21
好的,下面我为您提供一些代码示例,实现基于顺序查找表的顺序查找和二分查找算法。
顺序查找算法示例代码:
```python
def sequential_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
```
二分查找算法示例代码:
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
接下来,我们可以使用两个不同大小的查找表进行两次理论和实际性能对比。具体实现代码如下:
```python
import time
# 生成随机数组
def generate_random_array(n):
import random
return [random.randint(0, 10000) for _ in range(n)]
# 第一次查找表长度为第二次查找表长度的十分之一
n1 = 100
n2 = 1000
arr1 = generate_random_array(n1)
arr2 = generate_random_array(n2)
# 对于第一个查找表,进行顺序查找和二分查找,并记录时间
start_time = time.time()
sequential_search(arr1, arr1[-1])
binary_search(arr1, arr1[-1])
end_time = time.time()
time1 = end_time - start_time
# 对于第二个查找表,进行顺序查找,并记录时间
start_time = time.time()
sequential_search(arr2, arr2[-1])
end_time = time.time()
time2 = end_time - start_time
# 调整第二个查找表的长度,使得第一次查找表的长度为第二次查找表长度的十分之一
n2 = n1 * 10
arr2 = generate_random_array(n2)
# 对于第二个查找表,再次进行顺序查找,并记录时间
start_time = time.time()
sequential_search(arr2, arr2[-1])
end_time = time.time()
time3 = end_time - start_time
# 输出实验结果
print("第一次查找表长度为{},第二次查找表长度为{}。".format(n1, n2))
print("第一次顺序查找和二分查找的时间为:{}s".format(time1))
print("第二次顺序查找的时间为:{}s".format(time2))
print("调整后第二次顺序查找的时间为:{}s".format(time3))
```
通过调整第二次查找表的长度,我们可以实现第一次查找表的长度为第二次查找表长度的十分之一。同时,我们可以记录两次实验的查找时间,并进行性能对比。根据实验结果,我们可以得出不同查找表大小对算法性能的影响。