暴力法

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

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

示例：线性搜索

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

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

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

该元素可能出现在任意索引位置。如果我们修改上述任务，改为查找指定数字的索引，再进一步扩展为不指定具体数字，而是寻找列表中最大值或最小值的索引，暴力法仍然会遍历整个列表。

以下是实现代码：

查找元素

1using System;
2
3public class Program
4{
5    /// <summary>
6    /// 该方法接收一个整数列表和要查找的关键值
7    /// </summary>
8    /// <param name="lst">一个整数列表</param>
9    /// <param name="key">要查找的关键值</param>
10    /// <returns>若存在则返回元素索引，否则返回 -1</returns>
11    public static int FindIndex(int[] lst, int key)
12    {
13        // 遍历列表中的每个元素
14        for (int i = 0; i < lst.Length; i++)
15        {
16            // 检查当前元素是否为目标值
17            if (lst[i] == key)
18            {
19                // 找到后返回其索引
20                return i;
21            }
22        }
23
24        return -1; // 未找到元素，返回 -1
25    }
26
27    // 测试代码
28    public static void Main()
29    {
30        int numberToSearch = 7;
31        int[] nums = { 2, 4, 6, 3, 5, 7, 9, 1, 8 };
32
33        Console.WriteLine("数字 " + numberToSearch + " 位于索引 " +
34                          FindIndex(nums, numberToSearch));
35    }
36}

查找最小值索引

1using System;
2
3public class Program
4{
5    /// <summary>
6    /// 该方法找出列表中最小元素的索引
7    /// </summary>
8    /// <param name="lst">一个整数列表</param>
9    /// <returns>最小元素的索引，若不存在则返回 -1</returns>
10    static int MinimumIndex(int[] lst)
11    {
12        // 初始化最小索引为 -1
13        int minIndex = -1;
14        
15        // 设置最小值为一个极大数
16        int minValue = int.MaxValue;
17
18        // 遍历列表中的每个元素
19        for (int i = 0; i < lst.Length; i++)
20        {
21            if (minValue > lst[i])
22            {
23                minValue = lst[i];
24                minIndex = i;
25            }
26        }
27
28        return minIndex;
29    }
30
31    // 测试代码
32    static void Main()
33    {
34        int[] nums = { 2, 4, 6, 3, 5, 7, 9, 1, 8 };
35        int min = MinimumIndex(nums);
36        
37        Console.WriteLine("列表中的最小数是 " + nums[min] + "，位于索引 " + min);
38    }
39}

查找最大值索引

1using System;
2
3public class Program
4{
5    /// <summary>
6    /// 该方法找出列表中最大元素的索引
7    /// </summary>
8    /// <param name="lst">一个整数列表</param>
9    /// <returns>最大元素的索引，若不存在则返回 -1</returns>
10    static int MaximumIndex(int[] lst)
11    {
12        // 初始化最大索引为 -1
13        int maxIndex = -1;
14        
15        // 设置最大值为一个极小数
16        int maxValue = int.MinValue;
17
18        // 遍历列表中的每个元素
19        for (int i = 0; i < lst.Length; i++)
20        {
21            if (maxValue < lst[i])
22            {
23                maxValue = lst[i];
24                maxIndex = i;
25            }
26        }
27
28        return maxIndex;
29    }
30
31    // 测试代码
32    static void Main()
33    {
34        int[] nums = { 2, 4, 6, 3, 5, 7, 9, 1, 8 };
35        int max = MaximumIndex(nums);
36        
37        Console.WriteLine("列表中的最大数是 " + nums[max] + "，位于索引 " + max);
38    }
39}

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

优点

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

缺点

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