Elemento mínimo en vector ordenado rotado

Introducción

En este laboratorio, crearemos un programa en C++ para encontrar el elemento mínimo en un vector ordenado rotado. Un vector ordenado puede rotarse en algún elemento pivote del que no tienes conocimiento previamente.

Skills Graph

Incluir las bibliotecas necesarias y declarar el espacio de nombres

Primero, necesitamos incluir las bibliotecas necesarias y declarar el espacio de nombres. Este código se escribirá en el archivo ~/project/main.cpp. El código completo para el Paso 1 se muestra a continuación:

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

Crear una función para encontrar el elemento mínimo

Crearemos una función llamada findMin para encontrar el elemento mínimo en el vector ordenado rotado. En esta función, recorreremos cada elemento del vector y comprobaremos si ese elemento es el elemento mínimo. La lógica para comprobar si el elemento es mínimo se explica en los comentarios del bloque de código. El código completo para el Paso 2 se muestra a continuación:

int findMin(vector<int> &m)
{
    int i;
    int n = m.size();
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            // comprobar el primer elemento
            if (m[i] < m[n - 1] && m[i] < m[1])
                break;
        }
        else
        {
            // comprobar todos los demás elementos
            if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
                break;
        }
    }
    return m[i % n];
}

Escribir la función principal para probar el código

En la función principal, crearemos un vector llamado v y lo inicializaremos con algunos elementos. Luego, llamaremos a la función findMin para encontrar el elemento mínimo en el vector. Finalmente, imprimiremos el elemento mínimo. El código completo para el Paso 3 se muestra a continuación:

int main()
{
    vector<int> v = {4, 5, 6, 7, 1, 3, 2};
    int n = v.size();
    int minimum = 0;
    cout << "Los elementos del vector dado son: ";
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    minimum = findMin(v);
    cout << "\n\nEl elemento mínimo en el vector dado es: " << minimum << endl;
    return 0;
}

Compilar y ejecutar el código

En una ventana de terminal, navegue hasta el directorio donde se encuentra el archivo main.cpp usando el comando cd. Luego, compile el código usando el siguiente comando:

g++ main.cpp -o main

Si no hay errores, ejecute el ejecutable usando el siguiente comando:

./main

Debería ver la salida:

Los elementos del vector dado son: 4 5 6 7 1 3 2
El elemento mínimo en el vector dado es: 1

Esta salida confirma que nuestro código ha encontrado el elemento mínimo correcto en el vector.

Resumen

En este laboratorio, creamos un programa en C++ para encontrar el elemento mínimo en un vector ordenado rotado. Lo logramos recorriendo cada elemento del vector y comprobando si ese elemento es el elemento mínimo. Finalmente, imprimimos el elemento mínimo en la consola. Esperamos que hayas encontrado este laboratorio útil en tu camino para aprender programación.