Elemento Mínimo em Vetor Ordenado Rotacionado

Introdução

Neste laboratório, criaremos um programa C++ para encontrar o elemento mínimo em um vetor ordenado rotacionado. Um vetor ordenado pode ser rotacionado em algum elemento pivô desconhecido por você antecipadamente.

Incluir Bibliotecas Necessárias e Declarar Namespace

Primeiramente, precisamos incluir as bibliotecas necessárias e declarar o namespace. Este código será escrito no arquivo ~/project/main.cpp. O código completo para o Passo 1 é dado abaixo:

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

Criar uma Função para Encontrar o Elemento Mínimo

Criaremos uma função chamada findMin para encontrar o elemento mínimo no vetor ordenado rotacionado. Nesta função, iteraremos por cada elemento do vetor e verificaremos se esse elemento é o elemento mínimo. A lógica para verificar se o elemento é o mínimo é explicada nos comentários no bloco de código. O código completo para o Passo 2 é dado abaixo:

int findMin(vector<int> &m)
{
    int i;
    int n = m.size();
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            // check the first element
            if (m[i] < m[n - 1] && m[i] < m[1])
                break;
        }
        else
        {
            // check all other elements
            if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
                break;
        }
    }
    return m[i % n];
}

Escrever a Função Principal para Testar o Código

Na função principal, criaremos um vetor chamado v e o inicializaremos com alguns elementos. Em seguida, chamaremos a função findMin para encontrar o elemento mínimo no vetor. Finalmente, imprimiremos o elemento mínimo. O código completo para o Passo 3 é dado abaixo:

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;
}

Compilar e Executar o Código

Em uma janela de terminal, navegue até o diretório onde o arquivo main.cpp está localizado usando o comando cd. Em seguida, compile o código usando o seguinte comando:

g++ main.cpp -o main

Se não houver erros, execute o executável usando o seguinte comando:

./main

Você deverá ver a saída:

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

Esta saída confirma que nosso código encontrou o elemento mínimo correto no vetor.

Resumo

Neste laboratório, criamos um programa C++ para encontrar o elemento mínimo em um vetor ordenado rotacionado. Conseguimos isso iterando por cada elemento no vetor e verificando se esse elemento é o elemento mínimo. Finalmente, imprimimos o elemento mínimo no console. Esperamos que você tenha achado este laboratório útil em sua jornada para aprender programação.