旋转排序向量中的最小元素

介绍

在本实验中，我们将创建一个 C++ 程序来查找旋转排序向量中的最小元素。一个排序向量可以在某个未知的枢轴元素处进行旋转。

Skills Graph

包含必要的库并声明命名空间

首先，我们需要包含必要的库并声明命名空间。这段代码将写在 ~/project/main.cpp 文件中。以下是第一步的完整代码：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

创建函数以查找最小元素

我们将创建一个名为 findMin 的函数，用于查找旋转排序向量中的最小元素。在这个函数中，我们将遍历向量中的每个元素，并检查该元素是否为最小元素。检查元素是否为最小元素的逻辑在代码块的注释中进行了解释。以下是第二步的完整代码：

int findMin(vector<int> &m)
{
    int i;
    int n = m.size();
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            // 检查第一个元素
            if (m[i] < m[n - 1] && m[i] < m[1])
                break;
        }
        else
        {
            // 检查其他所有元素
            if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
                break;
        }
    }
    return m[i % n];
}

编写主函数以测试代码

在主函数中，我们将创建一个名为 v 的向量，并用一些元素初始化它。然后，我们将调用 findMin 函数来查找向量中的最小元素。最后，我们将打印最小元素。以下是第三步的完整代码：

int main()
{
    vector<int> v = {4, 5, 6, 7, 1, 3, 2};
    int n = v.size();
    int minimum = 0;
    cout << "The elements of the given vector are: ";
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    minimum = findMin(v);
    cout << "\n\nThe Minimum element in the given vector is: " << minimum << endl;
    return 0;
}

编译并运行代码

在终端窗口中，使用 cd 命令导航到 main.cpp 文件所在的目录。然后，使用以下命令编译代码：

g++ main.cpp -o main

如果没有错误，使用以下命令运行生成的可执行文件：

./main

你应该会看到以下输出：

The elements of the given vector are: 4 5 6 7 1 3 2
The Minimum element in the given vector is: 1

此输出确认我们的代码已正确找到向量中的最小元素。

总结

在本实验中，我们创建了一个 C++ 程序来查找旋转排序向量中的最小元素。我们通过遍历向量中的每个元素并检查该元素是否为最小元素来实现这一目标。最后，我们将最小元素打印到控制台。希望这个实验对你的编程学习之旅有所帮助。