# Find the minimum element in a sorted and rotated array

The problem about revolves around finding the minimum element in a sorted and rotated array. This situation arises when an initially sorted array is rotated at some point, disrupting its sorted order. Your goal is to efficiently identify the smallest element in this sorted and rotated array.

## Problem Statement

Given a sorted and rotated array `arr`, you need to determine the smallest element within it. This involves finding the point of rotation where the sorting order changes.

## Example

Consider the sorted and rotated array `arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]`. The minimum element in this array is `1`, as it represents the point of rotation.

## Idea to Solve

To efficiently find the minimum element in a sorted and rotated array, we can modify the binary search algorithm. The key insight is to check whether the middle element is the minimum element by comparing it with its neighbors. Depending on the comparison, we move towards the unsorted portion where the rotation point exists.

## Pseudocode

``````function findMin(arr, low, high):
if low > high:
return 0
if low == high:
return low
mid = low + (high - low) / 2
if mid < high and arr[mid + 1] < arr[mid]:
return mid + 1
else if mid > low and arr[mid] < arr[mid - 1]:
return mid
else:
a = findMin(arr, low, mid)
b = findMin(arr, mid + 1, high)
if arr[a] < arr[b]:
return a
else:
return b``````

## Algorithm Explanation

• The base cases check for invalid sub-arrays and return appropriate values.
• The middle index `mid` is calculated to divide the current sub-array into two halves.
• We compare the element at `mid` with its neighbors to identify whether `mid` is the minimum element.
• If `mid` is the minimum element, we return its index.
• If the left half (from `low` to `mid`) is sorted, and if the element after `mid` is smaller than `mid`, it indicates that the minimum element lies in the right unsorted portion.
• Similarly, if the right half (from `mid` to `high`) is sorted and the element before `mid` is greater than `mid`, it indicates that the minimum element lies in the left unsorted portion.
• If none of the above conditions are satisfied, it means there might be duplicate elements in the array, and we need to compare the minimum element found in the left and right halves to determine the true minimum.

## Code Solution

``````//  C program for
//  Find the minimum element in a sorted and rotated array
#include <stdio.h>
//Display array elements
void display(int arr[], int n)
{
printf("\n\n Array Elements \n [");
for (int i = 0; i < n; ++i)
{
printf("   %d", arr[i]);
}
printf("  ]\n");
}
// Find min element in array
int findMin(int arr[], int low, int high)
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
int mid = low + ((high - low) / 2);
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
int a = findMin(arr, low, mid);
int b = findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
void minElement(int arr[], int size)
{
int index = 0;
if (size > 1)
{
index = findMin(arr, 0, size - 1);
}
printf(" Min Element %d \n", arr[index]);
}
int main(int argc, char const *argv[])
{
// Defining sorted and rotated array of integer element
int arr1[] = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int arr2[] = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 2 , 9 , 10
};
int arr3[] = {
2 , 2 , 5 , -1 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2
};
// Get the size
int size = sizeof(arr1) / sizeof(arr1[0]);
display(arr1, size);
minElement(arr1, size);
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
display(arr2, size);
// Test Case B
minElement(arr2, size);
// Get the size
size = sizeof(arr3) / sizeof(arr3[0]);
display(arr3, size);
// Test Case C
minElement(arr3, size);
return 0;
}``````

#### Output

`````` Array Elements
[   7   8   9   1   2   3   4   5   6  ]
Min Element 1

Array Elements
[   11   22   43   45   51   62   73   2   9   10  ]
Min Element 2

Array Elements
[   2   2   5   -1   2   2   2   2   2   2   2   2  ]
Min Element -1``````
``````// Java Program
// Find the minimum element in a sorted and rotated array
public class Searching
{
//Display array elements
public void display(int[] arr, int n)
{
System.out.print("\n\n Array Elements \n [");
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print(" ]\n");
}
// Find min element in array
public int findMin(int[] arr, int low, int high)
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
int mid = low + ((high - low) / 2);
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
int a = findMin(arr, low, mid);
int b = findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
public void minElement(int[] arr, int size)
{
int index = 0;
if (size > 1)
{
index = findMin(arr, 0, size - 1);
}
System.out.println(" Min Element " + arr[index]);
}
public static void main(String args[])
{
// Defining sorted and rotated array of integer element
int[] arr1 = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int[] arr2 = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 2 , 9 , 10
};
int[] arr3 = {
2 , 2 , 5 , -1 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2
};
// Get the size
int size = arr1.length;
// Get the size
size = arr2.length;
// Test Case B
// Get the size
size = arr3.length;
// Test Case C
}
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Find the minimum element in a sorted and rotated array
class Searching
{
public:
//Display array elements
void display(int arr[], int n)
{
cout << "\n\n Array Elements \n [";
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << " ]\n";
}
// Find min element in array
int findMin(int arr[], int low, int high)
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
int mid = low + ((high - low) / 2);
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
int a = this->findMin(arr, low, mid);
int b = this->findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
void minElement(int arr[], int size)
{
int index = 0;
if (size > 1)
{
index = this->findMin(arr, 0, size - 1);
}
cout << " Min Element " << arr[index] << endl;
}
};
int main()
{
// Defining sorted and rotated array of integer element
int arr1[] = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int arr2[] = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 2 , 9 , 10
};
int arr3[] = {
2 , 2 , 5 , -1 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2
};
// Get the size
int size = sizeof(arr1) / sizeof(arr1[0]);
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
// Test Case B
// Get the size
size = sizeof(arr3) / sizeof(arr3[0]);
// Test Case C
return 0;
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````// Include namespace system
using System;
// Csharp Program
// Find the minimum element in a sorted and rotated array
public class Searching
{
//Display array elements
public void display(int[] arr, int n)
{
Console.Write("\n\n Array Elements \n [");
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write(" ]\n");
}
// Find min element in array
public int findMin(int[] arr, int low, int high)
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
int mid = low + ((high - low) / 2);
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
int a = this.findMin(arr, low, mid);
int b = this.findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
public void minElement(int[] arr, int size)
{
int index = 0;
if (size > 1)
{
index = this.findMin(arr, 0, size - 1);
}
Console.WriteLine(" Min Element " + arr[index]);
}
public static void Main(String[] args)
{
// Defining sorted and rotated array of integer element
int[] arr1 = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int[] arr2 = {
11 , 22 , 43 , 45 , 51 , 62 , 73 , 2 , 9 , 10
};
int[] arr3 = {
2 , 2 , 5 , -1 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2
};
// Get the size
int size = arr1.Length;
// Get the size
size = arr2.Length;
// Test Case B
// Get the size
size = arr3.Length;
// Test Case C
}
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````package main
import "fmt"
// Go Program
// Find the minimum element in a sorted and rotated array
type Searching struct {}
func getSearching() * Searching {
var me *Searching = &Searching {}
return me
}
//Display array elements
func(this Searching) display(arr[] int, n int) {
fmt.Print("\n\n Array Elements \n [")
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print(" ]\n")
}
// Find min element in array
func(this Searching) findMin(arr[] int, low int, high int) int {
if low > high {
return 0
}
if low == high {
return low
}
//Find middle element
var mid int = low + ((high - low) / 2)
if mid < high && arr[mid + 1] < arr[mid] {
return mid + 1
} else if mid > low && arr[mid] < arr[mid - 1] {
return mid
} else {
// When have exists duplicate elements
var a int = this.findMin(arr, low, mid)
var b int = this.findMin(arr, mid + 1, high)
if arr[a] < arr[b] {
return a
} else {
return b
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
func(this Searching) minElement(arr[] int, size int) {
var index int = 0
if size > 1 {
index = this.findMin(arr, 0, size - 1)
}
fmt.Println(" Min Element ", arr[index])
}
func main() {
var task * Searching = getSearching()
// Defining sorted and rotated array of integer element
var arr1 = [] int {
7,
8,
9,
1,
2,
3,
4,
5,
6,
}
var arr2 = [] int {
11,
22,
43,
45,
51,
62,
73,
2,
9,
10,
}
var arr3 = [] int {
2,
2,
5,
-1,
2,
2,
2,
2,
2,
2,
2,
2,
}
// Get the size
var size int = len(arr1)
// Get the size
size = len(arr2)
// Test Case B
// Get the size
size = len(arr3)
// Test Case C
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````<?php
// Php Program
// Find the minimum element in a sorted and rotated array
class Searching
{
//Display array elements
public	function display(\$arr, \$n)
{
echo("\n\n Array Elements \n [");
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
echo(" ]\n");
}
// Find min element in array
public	function findMin(\$arr, \$low, \$high)
{
if (\$low > \$high)
{
return 0;
}
if (\$low == \$high)
{
return \$low;
}
//Find middle element
\$mid = \$low + ((int)((\$high - \$low) / 2));
if (\$mid < \$high && \$arr[\$mid + 1] < \$arr[\$mid])
{
return \$mid + 1;
}
else if (\$mid > \$low && \$arr[\$mid] < \$arr[\$mid - 1])
{
return \$mid;
}
else
{
// When have exists duplicate elements
\$a = \$this->findMin(\$arr, \$low, \$mid);
\$b = \$this->findMin(\$arr, \$mid + 1, \$high);
if (\$arr[\$a] < \$arr[\$b])
{
return \$a;
}
else
{
return \$b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
public	function minElement(\$arr, \$size)
{
\$index = 0;
if (\$size > 1)
{
\$index = \$this->findMin(\$arr, 0, \$size - 1);
}
echo(" Min Element ".\$arr[\$index]."\n");
}
}

function main()
{
// Defining sorted and rotated array of integer element
\$arr1 = array(7, 8, 9, 1, 2, 3, 4, 5, 6);
\$arr2 = array(11, 22, 43, 45, 51, 62, 73, 2, 9, 10);
\$arr3 = array(2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2);
// Get the size
\$size = count(\$arr1);
// Get the size
\$size = count(\$arr2);
// Test Case B
// Get the size
\$size = count(\$arr3);
// Test Case C
}
main();``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````// Node JS Program
// Find the minimum element in a sorted and rotated array
class Searching
{
//Display array elements
display(arr, n)
{
process.stdout.write("\n\n Array Elements \n [");
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write(" ]\n");
}
// Find min element in array
findMin(arr, low, high)
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
var mid = low + (parseInt((high - low) / 2));
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
var a = this.findMin(arr, low, mid);
var b = this.findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
minElement(arr, size)
{
var index = 0;
if (size > 1)
{
index = this.findMin(arr, 0, size - 1);
}
console.log(" Min Element " + arr[index]);
}
}

function main()
{
// Defining sorted and rotated array of integer element
var arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6];
var arr2 = [11, 22, 43, 45, 51, 62, 73, 2, 9, 10];
var arr3 = [2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2];
// Get the size
var size = arr1.length;
// Get the size
size = arr2.length;
// Test Case B
// Get the size
size = arr3.length;
// Test Case C
}
main();``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````#  Python 3 Program
#  Find the minimum element in a sorted and rotated array
class Searching :
# Display list elements
def display(self, arr, n) :
print("\n\n Array Elements \n [", end = "")
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1

print(" ]")

#  Find min element in list
def findMin(self, arr, low, high) :
if (low > high) :
return 0

if (low == high) :
return low

# Find middle element
mid = low + (int((high - low) / 2))
if (mid < high and arr[mid + 1] < arr[mid]) :
return mid + 1
elif (mid > low and arr[mid] < arr[mid - 1]) :
return mid
else :
#  When have exists duplicate elements
a = self.findMin(arr, low, mid)
b = self.findMin(arr, mid + 1, high)
if (arr[a] < arr[b]) :
return a
else :
return b

#  Handles the request of finding min element in list
#  We assume that given list is sorted and rotated.
def minElement(self, arr, size) :
index = 0
if (size > 1) :
index = self.findMin(arr, 0, size - 1)

print(" Min Element ", arr[index])

def main() :
#  Defining sorted and rotated list of integer element
arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]
arr2 = [11, 22, 43, 45, 51, 62, 73, 2, 9, 10]
arr3 = [2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2]
#  Get the size
size = len(arr1)
#  Get the size
size = len(arr2)
#  Test Case B
#  Get the size
size = len(arr3)
#  Test Case C

if __name__ == "__main__": main()``````

#### Output

`````` Array Elements
[  7  8  9  1  2  3  4  5  6 ]
Min Element  1

Array Elements
[  11  22  43  45  51  62  73  2  9  10 ]
Min Element  2

Array Elements
[  2  2  5  -1  2  2  2  2  2  2  2  2 ]
Min Element  -1``````
``````#  Ruby Program
#  Find the minimum element in a sorted and rotated array
class Searching
# Display array elements
def display(arr, n)
print("\n\n Array Elements \n [")
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end

print(" ]\n")
end

#  Find min element in array
def findMin(arr, low, high)
if (low > high)
return 0
end

if (low == high)
return low
end

# Find middle element
mid = low + ((high - low) / 2)
if (mid < high && arr[mid + 1] < arr[mid])
return mid + 1
elsif (mid > low && arr[mid] < arr[mid - 1])
return mid
else

#  When have exists duplicate elements
a = self.findMin(arr, low, mid)
b = self.findMin(arr, mid + 1, high)
if (arr[a] < arr[b])
return a
else

return b
end

end

end

#  Handles the request of finding min element in array
#  We assume that given array is sorted and rotated.
def minElement(arr, size)
index = 0
if (size > 1)
index = self.findMin(arr, 0, size - 1)
end

print(" Min Element ", arr[index], "\n")
end

end

def main()
#  Defining sorted and rotated array of integer element
arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]
arr2 = [11, 22, 43, 45, 51, 62, 73, 2, 9, 10]
arr3 = [2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2]
#  Get the size
size = arr1.length
#  Get the size
size = arr2.length
#  Test Case B
#  Get the size
size = arr3.length
#  Test Case C
end

main()``````

#### Output

``````
Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1
``````
``````// Scala Program
// Find the minimum element in a sorted and rotated array
class Searching()
{
//Display array elements
def display(arr: Array[Int], n: Int): Unit = {
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print(" ]\n");
}
// Find min element in array
def findMin(arr: Array[Int], low: Int, high: Int): Int = {
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
var mid: Int = low + ((high - low) / 2);
if (mid < high && arr(mid + 1) < arr(mid))
{
return mid + 1;
}
else if (mid > low && arr(mid) < arr(mid - 1))
{
return mid;
}
else
{
// When have exists duplicate elements
var a: Int = findMin(arr, low, mid);
var b: Int = findMin(arr, mid + 1, high);
if (arr(a) < arr(b))
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
def minElement(arr: Array[Int], size: Int): Unit = {
var index: Int = 0;
if (size > 1)
{
index = findMin(arr, 0, size - 1);
}
println(" Min Element " + arr(index));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Searching = new Searching();
// Defining sorted and rotated array of integer element
var arr1: Array[Int] = Array(7, 8, 9, 1, 2, 3, 4, 5, 6);
var arr2: Array[Int] = Array(11, 22, 43, 45, 51, 62, 73, 2, 9, 10);
var arr3: Array[Int] = Array(2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2);
// Get the size
var size: Int = arr1.length;
// Get the size
size = arr2.length;
// Test Case B
// Get the size
size = arr3.length;
// Test Case C
}
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````
``````import Foundation;
// Swift 4 Program
// Find the minimum element in a sorted and rotated array
class Searching
{
//Display array elements
func display(_ arr: [Int], _ n: Int)
{
print("\n\n Array Elements \n [", terminator: "");
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(" ]");
}
// Find min element in array
func findMin(_ arr: [Int], _ low: Int, _ high: Int) -> Int
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
let mid: Int = low + ((high - low) / 2);
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
let a: Int = self.findMin(arr, low, mid);
let b: Int = self.findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
func minElement(_ arr: [Int], _ size: Int)
{
var index: Int = 0;
if (size > 1)
{
index = self.findMin(arr, 0, size - 1);
}
print(" Min Element ", arr[index]);
}
}
func main()
{
// Defining sorted and rotated array of integer element
let arr1: [Int] = [7, 8, 9, 1, 2, 3, 4, 5, 6];
let arr2: [Int] = [11, 22, 43, 45, 51, 62, 73, 2, 9, 10];
let arr3: [Int] = [2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2];
// Get the size
var size: Int = arr1.count;
// Get the size
size = arr2.count;
// Test Case B
// Get the size
size = arr3.count;
// Test Case C
}
main();``````

#### Output

`````` Array Elements
[  7  8  9  1  2  3  4  5  6 ]
Min Element  1

Array Elements
[  11  22  43  45  51  62  73  2  9  10 ]
Min Element  2

Array Elements
[  2  2  5  -1  2  2  2  2  2  2  2  2 ]
Min Element  -1``````
``````// Kotlin Program
// Find the minimum element in a sorted and rotated array
class Searching
{
//Display array elements
fun display(arr: Array < Int > , n: Int): Unit
{
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print(" ]\n");
}
// Find min element in array
fun findMin(arr: Array < Int > , low: Int, high: Int): Int
{
if (low > high)
{
return 0;
}
if (low == high)
{
return low;
}
//Find middle element
val mid: Int = low + ((high - low) / 2);
if (mid < high && arr[mid + 1] < arr[mid])
{
return mid + 1;
}
else if (mid > low && arr[mid] < arr[mid - 1])
{
return mid;
}
else
{
// When have exists duplicate elements
val a: Int = this.findMin(arr, low, mid);
val b: Int = this.findMin(arr, mid + 1, high);
if (arr[a] < arr[b])
{
return a;
}
else
{
return b;
}
}
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated.
fun minElement(arr: Array < Int > , size: Int): Unit
{
var index: Int = 0;
if (size > 1)
{
index = this.findMin(arr, 0, size - 1);
}
println(" Min Element " + arr[index]);
}
}
fun main(args: Array < String > ): Unit
{
// Defining sorted and rotated array of integer element
val arr1: Array < Int > = arrayOf(7, 8, 9, 1, 2, 3, 4, 5, 6);
val arr2: Array < Int > = arrayOf(11, 22, 43, 45, 51, 62, 73, 2, 9, 10);
val arr3: Array < Int > = arrayOf(2, 2, 5, -1, 2, 2, 2, 2, 2, 2, 2, 2);
// Get the size
var size: Int = arr1.count();
// Get the size
size = arr2.count();
// Test Case B
// Get the size
size = arr3.count();
// Test Case C
}``````

#### Output

`````` Array Elements
[ 7 8 9 1 2 3 4 5 6 ]
Min Element 1

Array Elements
[ 11 22 43 45 51 62 73 2 9 10 ]
Min Element 2

Array Elements
[ 2 2 5 -1 2 2 2 2 2 2 2 2 ]
Min Element -1``````

## Time Complexity

The time complexity of this algorithm depends on the number of recursive calls, which is logarithmic (`O(log n)`) due to the binary search nature.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.