暴力解法

暴力法

我们从最直接、最全面的方法——暴力法来讨论算法。这种方法要求我们遍历所有可能的情况，以找到问题的解。例如，如果我们有一个整数列表，并希望找出其中的最小值、最大值或某个特定元素，暴力法就需要遍历列表中的每一个元素，才能找到目标。

让我们通过一个例子来帮助你直观理解这一技术。

示例：线性查找

线性查找（也称顺序查找）是一种在给定列表中寻找目标值的方法。它按顺序检查列表中的每个元素，直到找到匹配的目标值，或者遍历完所有元素为止。线性查找在最坏情况下时间复杂度为线性时间，最多需要进行 n 次比较，其中 n 是列表的长度。

假设我们得到以下这个无序的整数列表：

现在，我们可能被要求在列表中查找某个特定元素，并返回是否存在该元素。使用暴力穷举搜索技术，我们的查找过程如下：

该元素存在于列表的某个特定索引位置。如果我们修改任务，比如不仅要找到指定数字的索引，还要进一步不指定具体数值，而是找出列表中最大值或最小值的索引，暴力法仍然会遍历整个列表。

以下是实现代码：

查找

1def find_index(lst, key):
2    """
3    该函数接收一个整数列表和要查找的关键值
4    :param lst: 一个整数列表
5    :param key: 要在列表中查找的值
6    :return: 若找到则返回元素的索引，否则返回 -1
7    """
8    
9    # 遍历列表中的每个元素
10    for i in range(len(lst)):
11        # 检查当前元素是否为目标值
12        if lst[i] == key:
13            # 找到后返回其索引
14            return i
15
16    return -1  # 未找到元素，返回 -1
17
18
19# 测试代码
20if __name__ == '__main__':
21    number_to_search = 7
22    nums = [2, 4, 6, 3, 5, 7, 9, 1, 8]
23    
24    print("数字", number_to_search, "位于索引",
25          find_index(nums, number_to_search))

最大值

1def maximum_index(lst):
2    """
3    函数用于查找列表中最大元素的索引
4    :param lst: 一个整数列表
5    :return: 最大元素的索引，若不存在则返回 -1
6    """
7    
8    # 初始化最大索引为 -1
9    max_index = -1
10    
11    # 设置最大值为极小数
12    max_val = -99999  # INT_MIN
13    
14    # 遍历列表中的每个元素
15    for i in range(len(lst)):
16        if max_val < lst[i]:
17            max_val = lst[i]
18            max_index = i
19
20    return max_index
21
22
23# 测试代码
24if __name__ == '__main__':
25    nums = [2, 4, 6, 3, 5, 7, 9, 1, 8]
26    
27    max_idx = maximum_index(nums)
28    print("列表中的最大数是", nums[max_idx], "，位于索引", max_idx)

最小值

1def minimum_index(lst):
2    """
3    该函数用于查找列表中最小元素的索引
4    :param lst: 一个整数列表
5    :return: 最小元素的索引，若不存在则返回 -1
6    """
7    
8    # 初始化最小索引为 -1
9    min_index = -1
10    
11    # 设置最小值为极大数
12    min_val = 9999
13    
14    # 遍历列表中的每个元素
15    for i in range(len(lst)):
16        if min_val > lst[i]:
17            min_val = lst[i]
18            min_index = i
19
20    return min_index
21
22
23# 测试代码
24if __name__ == '__main__':
25    nums = [2, 4, 6, 3, 5, 7, 9, 1, 8]
26    min_idx = minimum_index(nums)
27
28    print("列表中的最小数是", nums[min_idx], "，位于索引", min_idx)

时间复杂度： O(n) —— 在最坏情况下，如果我们要找的元素位于数组的最后一个位置，则需要进行 n 次比较。

优点

暴力法的优点在于，只要问题存在解，我们就一定能找到。一旦有了基本的解决思路，就可以专注于优化效率。

缺点

尽管这可能是我们最先想到的解决方案，但它却是效率最低的方法。在此阶段没有任何捷径可走，也无法进行性能优化。