编写两段程序，要求其时间复杂度分别是n的平方和logn的两个程序，并分析其最好最坏以及平均情况

编写两段程序的时间复杂度：

1. 线性扫描的平方时间复杂度示例（O(n^2)）：

def quadratic_search(lst, target):
    for i in range(len(lst)):
        for j in range(i, len(lst)):
            if lst[i] == target or lst[j] == target:
                return (i, j)
    return -1

# 这个函数在最坏、最好和平均情况下，都需要遍历列表中的所有元素对，所以时间复杂度都是 O(n^2)。

这个函数如查找目标值在二维数组或矩阵中的位置，每次内部循环都要检查当前行的所有元素。

2. 二分查找的对数时间复杂度示例（O(log n)）：

import bisect

def binary_search(sorted_list, target):
    pos = bisect.bisect_left(sorted_list, target)
    if pos != len(sorted_list) and sorted_list[pos] == target:
        return pos
    else:
        return -1

# 对于已排序的列表，二分查找在每一步都将搜索范围减半，所以在最坏、最好和平均情况下，时间复杂度都是 O(log n)。

这个函数通过递归地将有序列表分成两部分来进行查找，直到找到目标或确定不存在。

**分析：**
- 最好情况：当目标值恰好位于列表中间时，二分查找最快，只需 log n 步完成。
- 最坏情况：目标值不在列表中，或者在列表的第一个或最后一个元素，二分查找需要 log n 步才能确定。
- 平均情况：因为每次操作都把搜索空间缩小一半，平均而言，二分查找的步骤也是接近 log n 的。