暴力解法

暴力法

我们讨论算法时，可以从最直接、最全面的方法开始——解决一个问题的暴力法。这种方法要求我们遍历所有可能的情况，以找到问题的解。例如，如果我们有一个整数数组，并希望找出其中的最小值、最大值或某个特定元素，那么暴力法就需要遍历数组中的每一个元素来寻找目标。在这个阶段，没有捷径可走，也没有性能上的优化。

尽管这种解决问题的方法是最低效的，但它往往是人们最先想到的方案。此外，暴力法的一个优点是：只要问题存在解，我们一定能通过这种方式找到它。一旦我们有了基本的解决方案，就可以专注于如何让这个解变得更高效。

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

线性查找

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

假设我们得到如下一个无序的整数数组：

现在我们可以被要求在数组中查找某个特定元素，并返回其索引。该元素可以是任意整数值，也可以是数组中的最大值或最小值。

这就是使用暴力穷举法进行搜索的过程：

以下是实现该逻辑的代码：

查找指定元素

1#include <iostream>
2using namespace std;
3
4int find_index(int*, int, int);
5int find_element(int nums[], int number_to_search, int array_size){
6  cout << "数字 " << number_to_search << " 的索引位置是 " << find_index(nums, number_to_search, array_size) << endl;
7}	
8
9int main(){
10	int number_to_search = 7; 
11	int array_size = 9;
12  int nums[] = {2, 4, 6, 3, 5, 7, 9, 1, 8};
13	find_element(nums, number_to_search, array_size);
14  return 0;
15}
16
17// 接收一个整数数组和要查找的整数
18// 若存在则返回元素的索引，否则返回 -1
19int find_index(int array[], int to_find, int array_size) {
20  // 遍历数组中的每一个元素
21  for(int i = 0; i < array_size; i++){
22    // 检查当前元素是否为目标值
23    if (array[i] == to_find){
24      // 找到后返回其索引
25      return i;
26    }
27  }
28  return -1; // 未找到，返回 -1
29}
30// 不要取消注释 —— 仅作参考
31// 数组 = [2, 4, 6, 3, 5, 7, 9, 1, 8]

查找最大值

1#include <iostream>
2#include <limits.h>
3using namespace std;
4
5int maximum_index(int*, int);
6int find_element(int nums[], int array_size){
7  int maxx = maximum_index(nums, array_size);
8  cout << "数组中的最大值是 " << nums[maxx] << "，位于索引 " << maxx << endl;
9}	
10
11int main(){
12	int array_size = 9;
13  int nums[] = {2, 4, 6, 3, 5, 7, 9, 1, 8};
14	find_element(nums, array_size);
15  return 0;
16}
17
18// 接收一个数组，返回其中最大值的索引
19int maximum_index(int array[], int array_size) {
20  // 初始化最大值索引为 -1
21  int max_index = -1;
22  // 将最大值设为最小可能值
23  int max_val = INT_MIN;
24  // 遍历数组中的每个元素
25  for(int i = 0; i < array_size; i++){
26    if (max_val < array[i]) {
27      max_val = array[i];
28      max_index = i;
29    }
30  }
31  return max_index;
32}
33// 不要取消注释 —— 仅作参考
34// 数组 = [2, 4, 6, 3, 5, 7, 9, 1, 8]

查找最小值

1#include <iostream>
2#include <limits.h>
3using namespace std;
4
5int minimum_index(int*, int);
6int find_element(int nums[], int array_size){
7  int minn = minimum_index(nums, array_size);
8  cout << "数组中的最小值是 " << nums[minn] << "，位于索引 " << minn << endl;
9}	
10
11int main(){
12	int array_size = 9;
13  int nums[] = {2, 4, 6, 3, 5, 7, 9, 1, 8};
14	find_element(nums, array_size);
15  return 0;
16}
17
18// 接收一个数组，返回其中最小值的索引
19int minimum_index(int array[], int array_size) {
20  // 初始化最小值索引为 -1
21  int min_index = -1;
22  // 将最小值设为最大可能值
23  int min_val = INT_MAX;
24  // 遍历数组中的每个元素
25  for(int i = 0; i < array_size; i++){
26    if (min_val > array[i]) {
27      min_val = array[i];
28      min_index = i;
29    }
30  }
31  return min_index;
32}
33// 不要取消注释 —— 仅作参考
34// 数组 = [2, 4, 6, 3, 5, 7, 9, 1, 8]

时间复杂度： O(n) —— 因为在最坏情况下，我们需要对每个元素检查一次。