# Find the minimum element in a sorted and rotated array

C++ implementation to find the minimum element in a sorted and rotated array using multiple approaches.
Submitted by Vikneshwar GK, on February 26, 2022

Consider a sorted integer array, of size n, that has distinct elements and sorted at some unknown points. The task at hand is to find the minimum element in this array.

Example:

```Input:
array[]= {4, 5, 1, 2, 3}

Output:
Minimum element: 1

Input:
array[]= {60, 70, 30, 40, 50}

Output:
Minimum element: 30
```

Solution 1: Using Binary Search

This is a simple yet efficient approach to find the minimum element in a sorted and rotated array. On observing the array, we can notice that the minimum element is the one that has a previous element greater than itself, i.e., array[i-1]>array[i]. If there is no element like this, then the first element is the minimum element.

• Find the mid value of the array and compare it with mid-1 and mid+1
• If mid element is lesser than the last element, then the minimum element lies in the first half
• If mid element is greater than the last element, then the minimum element lies in the other half

C++ Implementation:

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

// Function to find the minimum value
// in sorted and rotated array
int findMin(int array[], int low, int high)
{
// if array is not rotated
if (high < low)
return array;

// if array contains only one element
if (high == low)
return array[low];

// Find mid
int mid = low + (high - low) / 2;

// check if minimum element is present at
// mid+1 and mid-1
if (mid < high && array[mid + 1] < array[mid])
return array[mid + 1];

if (mid > low && array[mid] < array[mid - 1])
return array[mid];

// if minimum present in the left half
if (array[high] > array[mid])
return findMin(array, low, mid - 1);
// if minimum present in the right half
return findMin(array, mid + 1, high);
}

// Main function
int main()
{
int array, N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}

cout << "Minimum element: " << findMin(array, 0, N - 1);

return 0;
}
```

Output:

```Enter Number of elements: 5
Enter element 1: 4
Enter element 2: 5
Enter element 3: 6
Enter element 4: 1
Enter element 5: 2
Minimum element: 1
```

Time Complexity: O(log(n)), where n is the length of the array.

Special Case - Handling duplicate elements

This is a space efficient approach that will not use a temporary array to perform the rotation for multiple k values.

C++ Implementation:

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

// Function to find the minimum value
// in sorted and rotated array
int findMin(int array[], int low, int high)
{
while (low < high) {
int mid = low + (high - low) / 2;
if (array[mid] == array[high])
high--;
else if (array[mid] > array[high])
low = mid + 1;
else
high = mid;
}
return array[high];
}

// Main function
int main()
{
int array, N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}

cout << "Minimum element: " << findMin(array, 0, N - 1);

return 0;
}
```

Output:

```Enter Number of elements: 6
Enter element 1: 4
Enter element 2: 5
Enter element 3: 5
Enter element 4: 1
Enter element 5: 2
Enter element 6: 3
Minimum element: 1
```

Time Complexity: O(log(n)), where n is the length of the array.

Preparation

What's New

Top Interview Coding Problems/Challenges!