【C++】B2093 查找特定的值

💯前言

• 在编写程序时，数组是最常用的数据结构之一。我们常常需要对数组进行遍历、查找或操作，而在竞赛和算法题中，数组的用法更加广泛。本次讨论的题目是关于数组中查找特定值的经典问题，它不仅考察基本的数组操作，还涉及对程序逻辑和优化的理解。在本文中，我们将详细解读题目，分析不同的解法及其优劣，并从多个角度拓展与优化。
  C++ 参考手册
  

💯题目描述

B2093 查找特定的值

在一个序列（下标从 0 开始）中查找一个给定的值，输出第一次出现的位置。

输入格式

1. 第一行包含一个正整数 $n$，表示序列中元素个数。
   • $1\le n\le 10,000$
2. 第二行包含 $n$ 个整数，依次给出序列中的每个元素，两个整数之间用单个空格隔开。
   • 元素的绝对值不超过 10,000。
3. 第三行包含一个整数 $x$，为需要查找的特定值。
   • $x$ 的绝对值不超过 10,000。

输出格式

若序列中存在 $x$，输出 $x$ 第一次出现的下标；否则输出 −1。

输入输出示例

输入：

5
2 3 6 7 3
3

输出：

1

输入：

5
1 2 3 4 5
6

输出：

-1

通过题目的描述，我们知道其核心目标是找到某个值在数组中的第一个下标（从 0 开始），并返回其位置，或在数组中不存在时返回 -1。

💯题目分析与解题思路

题目看似简单，但要在限定条件下写出清晰高效的代码，需要我们认真思考以下问题：

1. 输入处理：如何处理并存储数组和目标值？

   • 输入数据的长度 $n$ 和数组中的每个元素需要正确存储。
   • 对目标值 $x$ 的查找需要考虑数组的遍历顺序。

2. 逻辑设计：

   • 遍历数组时如何判断目标值是否存在？
   • 如果找到目标值，应如何处理下标？
   • 如果找不到，如何设计合理的输出逻辑？

3. 代码的优化：

   • 如何避免数组越界？
   • 如何提升代码的清晰度和运行效率？

接下来我们将详细分析两个解法——我的实现与老师的实现，并逐步优化。

💯代码实现与对比分析

我的实现代码

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    int m, find = 0;
    int index = 0;
    cin >> m;

    for (int a : arr)
    {
        if(a == m)
        {
            find++;
            cout << index << endl;
            break;
        }
        index++;    
    }

    if(find == 0)
        cout << -1 << endl;

    return 0;    
}

老师的实现代码

#include <iostream>
using namespace std;

const int N = 10010; // 定义数组最大长度为 10010
int arr[N]; // 静态数组

int main()
{
    int n = 0;
    cin >> n; // 输入数组长度

    for (int i = 0; i < n; i++) // 输入数组内容
    {
        cin >> arr[i];
    }

    int k = 0;
    cin >> k; // 输入需要查找的目标值

    int i = 0;
    for (i = 0; i < n; i++) // 遍历数组
    {
        if (k == arr[i]) // 如果找到目标值
        {
            cout << i << endl; // 输出目标值的下标
            break; // 跳出循环
        }
    }

    if (i == n) // 如果没有找到
        cout << -1 << endl;

    return 0;
}

详细对比与分析

1. 数组的定义方式

• 我的代码：

  int arr[n];
  

  • 使用动态数组，大小正好为 $n$。
  • 优点：节省内存，仅分配实际需要的空间。
  • 缺点：在旧版本 C++ 标准中，动态数组 int arr[n] 不被支持，可能出现兼容性问题。

• 老师的代码：

  const int N = 10010;
  int arr[N];
  

  • 使用静态数组，大小固定为 10010。
  • 优点：兼容性更好，保证了程序稳定运行，避免数组越界。
  • 缺点：在实际使用中可能浪费部分内存。

优化建议：如果使用现代 C++ 标准（如 C++11 及之后），推荐使用 std::vector 代替静态或动态数组。

2. 遍历与查找逻辑

• 我的代码：

  for (int a : arr)
  {
      if(a == m)
      {
          find++;
          cout << index << endl;
          break;
      }
      index++;    
  }
  

  • 使用了范围 for 循环，语法简洁。
  • 设置了额外变量 find 作为标志位。
  • 优点：代码较为现代化，适合用 std::vector。
  • 缺点：find 变量是多余的，完全可以通过循环的控制逻辑避免。

• 老师的代码：

  for (i = 0; i < n; i++) // 遍历数组
  {
      if (k == arr[i]) // 如果找到目标值
      {
          cout << i << endl; // 输出目标值的下标
          break; // 跳出循环
      }
  }
  if (i == n) // 如果没有找到
      cout << -1 << endl;
  

  • 使用经典 for 循环，判断循环变量是否超出范围。
  • 优点：逻辑直观，不需要额外标志位。
  • 缺点：需要检查 i == n，稍显冗余。

优化建议：使用 return 提前退出，可以进一步简化逻辑。

3. 输出逻辑

• 我的代码：

  if(find == 0)
      cout << -1 << endl;
  

  • 使用 find 标志判断是否输出 -1。

• 老师的代码：

  if (i == n)
      cout << -1 << endl;
  

  • 直接通过循环变量判断是否找到。

优化建议：结合遍历逻辑，直接在找到目标值时退出程序，减少多余检查。

💯最终优化实现

以下是结合两者优点并优化后的代码：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> arr(n); // 动态数组
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int k;
    cin >> k;

    for (int i = 0; i < n; i++) {
        if (arr[i] == k) {
            cout << i << endl; // 输出下标
            return 0; // 找到后直接退出程序
        }
    }

    cout << -1 << endl; // 未找到
    return 0;
}

改进点总结：

1. 使用现代 C++ 的 std::vector 代替普通数组，动态管理内存，安全高效。
2. 遍历时直接通过 return 提前退出，逻辑更加简洁。
3. 减少多余变量 find 和冗余检查，代码更加紧凑。

💯扩展与深入

1. 时间与空间复杂度分析

• 时间复杂度：

  • 本题的核心逻辑是对数组的线性遍历，时间复杂度为 $O(n)$。
  • 在最坏情况下（目标值不在数组中），需要遍历整个数组。

• 空间复杂度：

  • 如果使用静态数组，空间复杂度为 $O(n)$。
  • 如果使用动态数组（如 std::vector），额外的空间开销也为 $O(n)$。

2. 常见错误与调试技巧

• 数组越界：

  • 确保数组的大小正确定义，避免访问未分配的内存。
  • 在循环遍历时，条件应严格限制在数组范围内。

• 输入边界情况：

  • 测试输入数组为空（即 $n=0$）。
  • 测试目标值位于数组的开头和结尾。

3. 拓展问题

• 变体问题：
  • 如果需要查找所有出现目标值的位置，可以将下标存入一个结果数组。
  • 如果需要返回目标值的最后一次出现位置，可以反向遍历数组。

💯小提示：数组操作注意事项

1. 下标管理：

   • 有些题目要求从下标 0 开始存储数据，有些则从下标 1 开始。需要注意开辟足够的空间，避免数组越界。
   • 如果题目要求从下标 1 开始，可以额外分配一个位置，比如 int arr[n+1]，让下标 0 空出。

2. 预留空间：

   • 数组空间的开辟建议留出额外的空间，防止越界。例如，当需要存储 $n$ 个数据时，预留 $n+10$ 空间。浪费一点内存通常不会对性能产生太大影响，但能提高程序安全性。

3. 局部数组与全局数组：

   • 局部数组存储在栈区，空间有限，定义过大的局部数组可能导致栈溢出。对于较大的数组，建议使用全局数组（存储在静态区）或者动态数组（如 std::vector）。

💯小结

本文通过一个经典的数组查找问题，分析了不同实现方案及其优化方法。通过对代码逻辑、时间复杂度和空间复杂度的全面解析，我们总结出以下关键点：

1. 清晰的逻辑是解决问题的基础。
2. 代码优化应注重减少冗余逻辑，提升效率。
3. 扩展与思考能帮助我们从更多维度理解问题。