Given a sorted array arr[] (may be distinct or may contain duplicates) of size N that is rotated at some unknown point, the task is to find the minimum element in it.
Examples:
Input: arr[] = {5, 6, 1, 2, 3, 4}
Output: 1
Explanation: 1 is the minimum element present in the array.
Input: arr[] = {1, 2, 3, 4}
Output: 1
Input: arr[] = {2, 1}
Output: 1
Find the minimum element in a sorted and rotated array using Linear Search:
A simple solution is to use linear search to traverse the complete array and find a minimum.
Follow the steps mentioned below to implement the idea:
- Declare a variable (say min_ele) to store the minimum value and initialize it with arr[0].
- Traverse the array from the start.
- Update the minimum value (min_ele) if the current element is less than it.
- Return the final value of min_ele as the required answer.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>
using namespace std;
int findMin(int arr[], int n)
{
int min_ele = arr[0];
for (int i = 0; i < n; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
int main()
{
int arr[] = { 5, 6, 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMin(arr, N) << endl;
return 0;
}
|
Java
import java.io.*;
class GFG {
static int findMin(int arr[], int n)
{
int min_ele = arr[0];
for (int i = 0; i < n; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
public static void main (String[] args) {
int arr[] = { 5, 6, 1, 2, 3, 4 };
int N = arr.length;
System.out.println(findMin(arr, N));
}
}
|
Python3
def findMin(arr, N):
min_ele = arr[0];
for i in range(N) :
if arr[i] < min_ele :
min_ele = arr[i]
return min_ele;
arr = [5, 6, 1, 2, 3, 4]
N = len(arr)
print(findMin(arr,N))
|
C#
using System;
class Minimum {
static int findMin(int[] arr, int N)
{
int min_ele = arr[0];
for (int i = 0; i < N; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
public static void Main()
{
int[] arr = { 5, 6, 1, 2, 3, 4 };
int N = arr.Length;
Console.WriteLine(findMin(arr, N));
}
}
|
Javascript
function findMin(arr, n) {
let min_ele = arr[0];
for (let i = 0; i < n; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
let arr = [5, 6, 1, 2, 3, 4];
let N = arr.length;
console.log(findMin(arr, N));
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the minimum element in a sorted and rotated array using Binary Search:
- The findMin function takes three arguments: arr (the input array), low (the lowest index of the array), and high (the highest index of the array).
- If the array is not rotated, i.e., the first element is less than or equal to the last element, then the first element is returned as the minimum element.
- Otherwise, a binary search algorithm is implemented to find the minimum element.
- The binary search loop continues until the low index is less than or equal to the high index.
- Inside the loop, the middle index mid is calculated as the average of the low and high indices.
- If the element at the mid index is less than the element at mid-1 index, then the element at the mid index is returned as the minimum element.
- If the element at the mid index is greater than the element at the high index, then the minimum element must be in the right half of the array. So, the low index is updated to mid+1.
- Otherwise, the minimum element must be in the left half of the array. So, the high index is updated to mid-1.
- If no minimum element is found during the binary search, then the findMin function returns None.
- In the driver program, an input array arr is defined with rotated and sorted elements, and the findMin function is called with low and high indices set to 0 and N-1, respectively, where N is the length of the input array.
- The minimum element is printed using the print function with the help of the str function to convert the returned value to a string
Illustration:
Let the array be arr = [7, 8, 9, 1, 2, 3, 4, 5, 6]. Here, the minimum element in the array is 1.
We start with low = 0 and high = 8.
First iteration:
mid = (low + high) // 2 = 4
arr[mid] = 2, arr[mid-1] = 1
arr[mid] < arr[mid-1], so we return arr[mid] which is 2.
So the minimum element is found at index 3 and arr[3] = 1.
Below is the code implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int findMin(vector<int>& arr, int low, int high)
{
if (arr[low] <= arr[high]) {
return arr[low];
}
while (low <= high) {
int mid = (low + high) / 2;
if (mid-1 >= 0 && arr[mid] < arr[mid - 1]) {
return arr[mid];
}
if (arr[mid] > arr[high]) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
int main()
{
vector<int> arr = { 5, 6, 1, 2, 3, 4 };
int N = arr.size();
cout << "The minimum element is "
<< findMin(arr, 0, N - 1) << endl;
return 0;
}
|
Java
import java.util.*;
public class Main {
public static int findMin(List<Integer> arr, int low,
int high)
{
if (arr.get(low) <= arr.get(high)) {
return arr.get(low);
}
while (low <= high) {
int mid = (low + high) / 2;
if (arr.get(mid) < arr.get(mid - 1)) {
return arr.get(mid);
}
if (arr.get(mid) > arr.get(high)) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args)
{
List<Integer> arr = new ArrayList<>(
Arrays.asList(5, 6, 1, 2, 3, 4));
int N = arr.size();
System.out.println("The minimum element is "
+ findMin(arr, 0, N - 1));
}
}
|
Python3
def findMin(arr, low, high):
if arr[low] <= arr[high]:
return arr[low]
while low <= high:
mid = (low + high) // 2
if arr[mid] < arr[mid-1]:
return arr[mid]
if arr[mid] > arr[high]:
low = mid + 1
else:
high = mid - 1
return None
if __name__ == '__main__':
arr = [5, 6, 1, 2, 3, 4]
N = len(arr)
print("The minimum element is " + \
str(findMin(arr, 0, N-1)))
|
C#
using System;
using System.Collections.Generic;
public class Program {
public static int findMin(List<int> arr, int low, int high) {
if (arr[low] <= arr[high]) {
return arr[low];
}
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] < arr[mid - 1]) {
return arr[mid];
}
if (arr[mid] > arr[high]) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
public static void Main() {
List<int> arr = new List<int> {5, 6, 1, 2, 3, 4};
int N = arr.Count;
Console.WriteLine("The minimum element is " + findMin(arr, 0, N - 1));
}
}
|
Javascript
function findMin(arr, low, high) {
if (arr[low] <= arr[high]) {
return arr[low];
}
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid] < arr[mid - 1]) {
return arr[mid];
}
if (arr[mid] > arr[high]) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return -1;
}
let arr = [5, 6, 1, 2, 3, 4];
let N = arr.length;
console.log("The minimum element is " + findMin(arr, 0, N - 1));
|
Output
The minimum element is 1
Time complexity: O(log n) – where n is the number of elements in the array. This is because the algorithm uses binary search, which has a logarithmic time complexity.
Auxiliary Space: O(1) – the algorithm uses a constant amount of extra space to store variables such as low, high, and mid, regardless of the size of the input array.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!