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++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum value
int findMin(int arr[], int n)
{
int min_ele = arr[0];
// Traversing over array to
// find minimum element
for (int i = 0; i < n; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
// Driver code
int main()
{
int arr[] = { 5, 6, 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << findMin(arr, N) << endl;
return 0;
}
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Function to find the minimum value
static int findMin(int arr[], int n)
{
int min_ele = arr[0];
// Traversing over array to
// find minimum element
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));
}
}
// This code is contributed by aadityaburujwale.
# python3 code to implement the approach
def findMin(arr, N):
min_ele = arr[0];
# Traversing over array to
# find minimum element
for i in range(N) :
if arr[i] < min_ele :
min_ele = arr[i]
return min_ele;
# Driver program
arr = [5, 6, 1, 2, 3, 4]
N = len(arr)
print(findMin(arr,N))
# This code is contributed by aditya942003patil
// C# code to implement above approach
using System;
class Minimum {
static int findMin(int[] arr, int N)
{
int min_ele = arr[0];
// Traversing over array to
// find minimum element
for (int i = 0; i < N; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
// Driver Program
public static void Main()
{
int[] arr = { 5, 6, 1, 2, 3, 4 };
int N = arr.Length;
Console.WriteLine(findMin(arr, N));
}
}
// This code is contributed by aditya942003patil.
// JS code to implement the approach
// Function to find the minimum value
function findMin(arr, n) {
let min_ele = arr[0];
// Traversing over array to
// find minimum element
for (let i = 0; i < n; i++) {
if (arr[i] < min_ele) {
min_ele = arr[i];
}
}
return min_ele;
}
// Driver code
let arr = [5, 6, 1, 2, 3, 4];
let N = arr.length;
// Function call
console.log(findMin(arr, N));
// This code is contributed by adityamaharshi21.
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the Minimum element in a Sorted and Rotated Array
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: 1Input: arr[] = {2, 1}
Output: 1