Minimum Element in Rotated Sorted Vector

Introduction

In this lab, we will create a C++ program to find the minimum element in a rotated sorted vector. A sorted vector can be rotated at some pivot element unknown to you beforehand.

Skills Graph

Include Necessary Libraries and Declare Namespace

First, we need to include the necessary libraries and declare the namespace. This code will be written in the ~/project/main.cpp file. The complete code for Step 1 is given below:

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

Create a Function to Find the Minimum Element

We will create a function named findMin to find the minimum element in the rotated sorted vector. In this function, we will loop through each element of the vector and check if that element is the minimum element. The logic for checking if the element is minimum is explained in the comments in the code block. The complete code for Step 2 is given below:

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

Write the Main Function to Test the Code

In the main function, we will create a vector named v and initialize it with some elements. Then, we will call the findMin function to find the minimum element in the vector. Finally, we will print the minimum element. The complete code for Step 3 is given below:

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

Compile and Run the Code

In a terminal window, navigate to the directory where the main.cpp file is located using the cd command. Then, compile the code using the following command:

g++ main.cpp -o main

If there are no errors, run the executable using the following command:

./main

You should see the output:

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

This output confirms that our code has found the correct minimum element in the vector.

Summary

In this lab, we created a C++ program to find the minimum element in a rotated sorted vector. We achieved this by looping through each element in the vector and checking if that element is the minimum element. Finally, we printed the minimum element to the console. We hope that you found this lab helpful in your journey to learn programming.