Posted on by Kalkicode
Code Array

# Find smallest element in sorted rotated array

First approach, we are find the largest element in sorted and rotated array. Next element of largest is always smallest (when array is sorted and rotated). This process is very simple and tack O(n) time.

``````//C Program
//Find smallest element in sorted rotated array
#include <stdio.h>

//Find minimum value in a rotated sorted array
void minimum(int arr[], int size)
{
if (size <= 1)
{
return;
}
int i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i++;
}
if (i + 1 < size)
{
printf(" Minimum : %d\n", arr[i + 1]);
}
else
{
printf(" Not an rotated sorted array\n");
}
}
//Display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%3d", arr[i]);
}
printf("\n");
}
int main()
{
//Define array elements
int arr[] = {
13 , 17 , 17 , 31 , 1 , 4 , 6 , 8 , 9 , 12
};
//Get the size of array
int size = (sizeof(arr) / sizeof(arr[0]));
display(arr, size);
minimum(arr, size);
return 0;
}``````

#### Output

`````` 13 17 17 31  1  4  6  8  9 12
Minimum : 1``````
``````/*
Java Program
Find smallest element in sorted rotated array
*/
public class SearchElement
{
//Display array element values
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  " + arr[i]);
}
System.out.print("\n");
}
//Find minimum value in a rotated sorted array
public void minimum(int[] arr, int size)
{
if (size <= 1)
{
return;
}
int i = 0;
//Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i++;
}
if (i + 1 < size)
{
System.out.print("  Minimum : " + arr[i + 1] + "\n");
}
else
{
System.out.print(" Not an rotated sorted array\n");
}
}
public static void main(String[] args)
{
SearchElement obj = new SearchElement();
//Define the value of array elements
int[] arr = {
13 , 17 , 17 , 31 , 1 , 4 , 6 , 8 , 9 , 12
};
//Get the size of array
int size = arr.length;
obj.display(arr, size);
obj.minimum(arr, size);
}
}``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````
``````// Include header file
#include <iostream>
using namespace std;

/*
C++ Program
Find smallest element in sorted rotated array
*/

class SearchElement
{
public:
// Display array element values
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "  " << arr[i];
}
cout << "\n";
}
// Find minimum value in a rotated sorted array
void minimum(int arr[], int size)
{
if (size <= 1)
{
return;
}
int i = 0;
// Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i++;
}
if (i + 1 < size)
{
cout << "  Minimum : " << arr[i + 1] << "\n";
}
else
{
cout << " Not an rotated sorted array\n";
}
}
};
int main()
{
SearchElement obj = SearchElement();
// Define the value of array elements
int arr[] = {
13 , 17 , 17 , 31 , 1 , 4 , 6 , 8 , 9 , 12
};
// Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.display(arr, size);
obj.minimum(arr, size);
return 0;
}``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````
``````// Include namespace system
using System;
/*
C# Program
Find smallest element in sorted rotated array
*/
public class SearchElement
{
// Display array element values
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write("  " + arr[i]);
}
Console.Write("\n");
}
// Find minimum value in a rotated sorted array
public void minimum(int[] arr, int size)
{
if (size <= 1)
{
return;
}
int i = 0;
// Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i++;
}
if (i + 1 < size)
{
Console.Write("  Minimum : " + arr[i + 1] + "\n");
}
else
{
Console.Write(" Not an rotated sorted array\n");
}
}
public static void Main(String[] args)
{
SearchElement obj = new SearchElement();
// Define the value of array elements
int[] arr = {
13 , 17 , 17 , 31 , 1 , 4 , 6 , 8 , 9 , 12
};
// Get the size of array
int size = arr.Length;
obj.display(arr, size);
obj.minimum(arr, size);
}
}``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````
``````<?php
/*
Php Program
Find smallest element in sorted rotated array
*/
class SearchElement
{
// Display array element values
public  function display( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$arr[\$i];
}
echo "\n";
}
// Find minimum value in a rotated sorted array
public  function minimum( & \$arr, \$size)
{
if (\$size <= 1)
{
return;
}
\$i = 0;
// Find largest element
while (\$i < \$size - 1 && \$arr[\$i] <= \$arr[\$i + 1])
{
\$i++;
}
if (\$i + 1 < \$size)
{
echo "  Minimum : ". \$arr[\$i + 1] ."\n";
}
else
{
echo " Not an rotated sorted array\n";
}
}
}

function main()
{
\$obj = new SearchElement();
// Define the value of array elements
\$arr = array(13, 17, 17, 31, 1, 4, 6, 8, 9, 12);
// Get the size of array
\$size = count(\$arr);
\$obj->display(\$arr, \$size);
\$obj->minimum(\$arr, \$size);
}
main();``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````
``````/*
Node Js Program
Find smallest element in sorted rotated array
*/
class SearchElement
{
// Display array element values
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + arr[i]);
}
process.stdout.write("\n");
}
// Find minimum value in a rotated sorted array
minimum(arr, size)
{
if (size <= 1)
{
return;
}
var i = 0;
// Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i++;
}
if (i + 1 < size)
{
process.stdout.write("  Minimum : " + arr[i + 1] + "\n");
}
else
{
process.stdout.write(" Not an rotated sorted array\n");
}
}
}

function main()
{
var obj = new SearchElement();
// Define the value of array elements
var arr = [13, 17, 17, 31, 1, 4, 6, 8, 9, 12];
// Get the size of array
var size = arr.length;
obj.display(arr, size);
obj.minimum(arr, size);
}
main();``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````
``````#   Python 3 Program
#   Find smallest element in sorted rotated array

class SearchElement :
#  Display array element values
def display(self, arr, size) :
i = 0
while (i < size) :
print("  ", arr[i], end = "")
i += 1

print(end = "\n")

#  Find minimum value in a rotated sorted array
def minimum(self, arr, size) :
if (size <= 1) :
return

i = 0
#  Find largest element
while (i < size - 1 and arr[i] <= arr[i + 1]) :
i += 1

if (i + 1 < size) :
print("  Minimum : ", arr[i + 1] )
else :
print(" Not an rotated sorted array")

def main() :
obj = SearchElement()
#  Define the value of array elements
arr = [13, 17, 17, 31, 1, 4, 6, 8, 9, 12]
#  Get the size of array
size = len(arr)
obj.display(arr, size)
obj.minimum(arr, size)

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

#### Output

``````   13   17   17   31   1   4   6   8   9   12
Minimum :  1``````
``````#   Ruby Program
#   Find smallest element in sorted rotated array

class SearchElement
#  Display array element values
def display(arr, size)
i = 0
while (i < size)
print("  ", arr[i])
i += 1
end

print("\n")
end

#  Find minimum value in a rotated sorted array
def minimum(arr, size)
if (size <= 1)
return
end

i = 0
#  Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
i += 1
end

if (i + 1 < size)
print("  Minimum : ", arr[i + 1] ,"\n")
else
print(" Not an rotated sorted array\n")
end

end

end

def main()
obj = SearchElement.new()
#  Define the value of array elements
arr = [13, 17, 17, 31, 1, 4, 6, 8, 9, 12]
#  Get the size of array
size = arr.length
obj.display(arr, size)
obj.minimum(arr, size)
end

main()``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1
``````
``````/*
Scala Program
Find smallest element in sorted rotated array
*/
class SearchElement
{
//  Display array element values
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + arr(i));
i += 1;
}
print("\n");
}
//  Find minimum value in a rotated sorted array
def minimum(arr: Array[Int], size: Int): Unit = {
if (size <= 1)
{
return;
}
var i: Int = 0;
//  Find largest element
while (i < size - 1 && arr(i) <= arr(i + 1))
{
i += 1;
}
if (i + 1 < size)
{
print("  Minimum : " + arr(i + 1) + "\n");
}
else
{
print(" Not an rotated sorted array\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: SearchElement = new SearchElement();
//  Define the value of array elements
var arr: Array[Int] = Array(13, 17, 17, 31, 1, 4, 6, 8, 9, 12);
//  Get the size of array
var size: Int = arr.length;
obj.display(arr, size);
obj.minimum(arr, size);
}
}``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````
``````/*
Swift 4 Program
Find smallest element in sorted rotated array
*/
class SearchElement
{
//  Display array element values
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
//  Find minimum value in a rotated sorted array
func minimum(_ arr: [Int], _ size: Int)
{
if (size <= 1)
{
return;
}
var i: Int = 0;
//  Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i += 1;
}
if (i + 1 < size)
{
print("  Minimum : ", arr[i + 1]);
}
else
{
print(" Not an rotated sorted array");
}
}
}
func main()
{
let obj: SearchElement = SearchElement();
//  Define the value of array elements
let arr: [Int] = [13, 17, 17, 31, 1, 4, 6, 8, 9, 12];
//  Get the size of array
let size: Int = arr.count;
obj.display(arr, size);
obj.minimum(arr, size);
}
main();``````

#### Output

``````   13   17   17   31   1   4   6   8   9   12
Minimum :  1``````
``````/*
Kotlin Program
Find smallest element in sorted rotated array
*/
class SearchElement
{
//  Display array element values
fun display(arr: Array<Int>, size: Int): Unit
{
var i: Int = 0;
while (i<size)
{
print("  " + arr[i]);
i += 1;
}
print("\n");
}
//  Find minimum value in a rotated sorted array
fun minimum(arr: Array<Int>, size: Int): Unit
{
if (size <= 1)
{
return;
}
var i: Int = 0;
//  Find largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
{
i += 1;
}
if (i + 1 < size)
{
print("  Minimum : " + arr[i + 1] + "\n");
}
else
{
print(" Not an rotated sorted array\n");
}
}
}
fun main(args: Array<String>): Unit
{
var obj: SearchElement = SearchElement();
//  Define the value of array elements
var arr: Array<Int> = arrayOf(13, 17, 17, 31, 1, 4, 6, 8, 9, 12);
//  Get the size of array
var size: Int = arr.count();
obj.display(arr, size);
obj.minimum(arr, size);
}``````

#### Output

``````  13  17  17  31  1  4  6  8  9  12
Minimum : 1``````

Better solution we can use binary search and find smallest element in array. This process are tack O(log n) time when elements are not repeated. When element array repeating there is difficult to find element in O(log n time). For Example .

``````Example 1
arr1[] = {3, 3, 3, 3, 3, 1, 2, 3}
O/p : 1
Example 2 :
arr2[] = {3, -7, 1, 3, 3, 3, 3, 3}
O/p : -7
Example 3:
arr2[] = {3, 3, 3, 3}
O/p : 3
``````

So in this situation time complexity will be O(n) time. Here given code implementation process.

``````//C Program
//Find smallest element in sorted rotated array
#include <stdio.h>

//Display array elements
void display(int arr[], int size)
{
printf("\n\n Array Elements \n [");
for (int i = 0; i < size; ++i)
{
printf("   %d", arr[i]);
}
printf("  ]\n");
}
//Returns the location of first smallest element in given range
int smallest(int arr[], int low, int high)
{
for (int i = low + 1; i < high; ++i)
{
if (arr[low] > arr[i])
{
return i;
}
}
return low;
}
//Find min element in array
int findMin(int arr[], int low, int high)
{
int mid = (low + high) / 2;
if (low == high)
{
return low;
}
if (arr[low] >= arr[high])
{
if (arr[mid] > arr[high])
{
return findMin(arr, mid + 1, high);
}
if (arr[mid] < arr[high])
{
return findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{
//For exampe
//x        x         x
//3  1  2  3   3  3  3
//or
//3  3  3  3   1  2  3
//or (all duplicate)
//3  3  3  3   3  3  3
return smallest(arr, low, high);
}
return low;
}
//Handles the request of finding min element in array
//We assume that given array is sorted and rotated
void minElement(int arr[], int size)
{
if (size <= 0)
{
return;
}
int location = 0;
if (size > 1)
{
location = findMin(arr, 0, size - 1);
}
printf(" Min Element %d \n", arr[location]);
}
int main()
{
//Defining sorted and rotated arrays of integer element
int arr1[] = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int arr2[] = {
15 , 17 , 3 , 4 , 5 , 7 , 8
};
int arr3[] = {
3 , 3 , 5 , 0 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3
};
int arr4[] = {
2 , 2 , 5 , 1 , 2
};
int arr5[] = {
2 , 2 , 2 , 2 , 2 , -1 , 2 , 2
};
//Get the size
int size = sizeof(arr1) / sizeof(arr1[0]);
//Case A
display(arr1, size);
minElement(arr1, size);
//Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
//Case B
display(arr2, size);
minElement(arr2, size);
//Get the size
size = sizeof(arr3) / sizeof(arr3[0]);
//Case C
display(arr3, size);
minElement(arr3, size);
//Get the size
size = sizeof(arr4) / sizeof(arr4[0]);
//Test Case D
display(arr4, size);
minElement(arr4, size);
//Get the size
size = sizeof(arr5) / sizeof(arr5[0]);
//Test Case E
display(arr5, size);
minElement(arr5, size);
return 0;
}``````

#### Output

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

Array Elements
[   15   17   3   4   5   7   8  ]
Min Element 3

Array Elements
[   3   3   5   0   2   3   3   3   3   3   3   3  ]
Min Element 0

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

Array Elements
[   2   2   2   2   2   -1   2   2  ]
Min Element -1``````
``````/*
Java program
Find smallest element in sorted rotated array
*/
public class SearchElement
{
//Display array elements
public void display(int[] arr, int size)
{
System.out.print("\n\n Array Elements \n [");
for (int i = 0; i < size; ++i)
{
System.out.print("  " + arr[i]);
}
System.out.print(" ]\n");
}
//Returns the location of first smallest element in given range
public int smallest(int[] arr, int low, int high)
{
for (int i = low + 1; i < high; ++i)
{
if (arr[low] > arr[i])
{
return i;
}
}
return low;
}
//Find min element in array
public int findMin(int[] arr, int low, int high)
{
int mid = (low + high) / 2;
if (low == high)
{
return low;
}
if (arr[low] >= arr[high])
{
if (arr[mid] > arr[high])
{
return findMin(arr, mid + 1, high);
}
if (arr[mid] < arr[high])
{
return findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{
//For exampe
//x        x         x
//3  1  2  3   3  3  3
//or
//3  3  3  3   1  2  3
//or (all duplicate)
//3  3  3  3   3  3  3
return smallest(arr, low, high);
}
return low;
}
//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)
{
if (size <= 0)
{
return;
}
int location = 0;
if (size > 1)
{
location = findMin(arr, 0, size - 1);
}
System.out.print(" Min Element " + arr[location] + " \n");
}
public static void main(String[] args)
{
SearchElement work = new SearchElement();
//Defining sorted and rotated arrays of integer element
int[] arr1 = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int[] arr2 = {
15 , 17 , 3 , 4 , 5 , 7 , 8
};
int[] arr3 = {
3 , 3 , 5 , 0 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3
};
int[] arr4 = {
2 , 2 , 5 , 1 , 2
};
int[] arr5 = {
2 , 2 , 2 , 2 , 2 , -1 , 2 , 2
};
//Get the size
int size = arr1.length;
//Case A
work.display(arr1, size);
work.minElement(arr1, size);
//Get the size
size = arr2.length;
//Case B
work.display(arr2, size);
work.minElement(arr2, size);
//Get the size
size = arr3.length;
//Case C
work.display(arr3, size);
work.minElement(arr3, size);
//Get the size
size = arr4.length;
//Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
//Get the size
size = arr5.length;
//Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
}
}``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program
Find smallest element in sorted rotated array
*/
class SearchElement
{
public:
// Display array elements
void display(int arr[], int size)
{
cout << "\n\n Array Elements \n [";
for (int i = 0; i < size; ++i)
{
cout << "  " << arr[i];
}
cout << " ]\n";
}
// Returns the location of first smallest element in given range
int smallest(int arr[], int low, int high)
{
for (int i = low + 1; i < high; ++i)
{
if (arr[low] > arr[i])
{
return i;
}
}
return low;
}
// Find min element in array
int findMin(int arr[], int low, int high)
{
int mid = (low + high) / 2;
if (low == high)
{
return low;
}
if (arr[low] >= arr[high])
{
if (arr[mid] > arr[high])
{
return this->findMin(arr, mid + 1, high);
}
if (arr[mid] < arr[high])
{
return this->findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{
// For exampe
// x        x         x
// 3  1  2  3   3  3  3
// or
// 3  3  3  3   1  2  3
// or (all duplicate)
// 3  3  3  3   3  3  3
return this->smallest(arr, low, high);
}
return low;
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated
void minElement(int arr[], int size)
{
if (size <= 0)
{
return;
}
int location = 0;
if (size > 1)
{
location = this->findMin(arr, 0, size - 1);
}
cout << " Min Element " << arr[location] << " \n";
}
};
int main()
{
SearchElement work = SearchElement();
// Defining sorted and rotated arrays of integer element
int arr1[] = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int arr2[] = {
15 , 17 , 3 , 4 , 5 , 7 , 8
};
int arr3[] = {
3 , 3 , 5 , 0 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3
};
int arr4[] = {
2 , 2 , 5 , 1 , 2
};
int arr5[] = {
2 , 2 , 2 , 2 , 2 , -1 , 2 , 2
};
// Get the size
int size = sizeof(arr1) / sizeof(arr1[0]);
// Case A
work.display(arr1, size);
work.minElement(arr1, size);
// Get the size
size = sizeof(arr2) / sizeof(arr2[0]);
// Case B
work.display(arr2, size);
work.minElement(arr2, size);
// Get the size
size = sizeof(arr3) / sizeof(arr3[0]);
// Case C
work.display(arr3, size);
work.minElement(arr3, size);
// Get the size
size = sizeof(arr4) / sizeof(arr4[0]);
// Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
// Get the size
size = sizeof(arr5) / sizeof(arr5[0]);
// Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
return 0;
}``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1``````
``````// Include namespace system
using System;
/*
C# program
Find smallest element in sorted rotated array
*/
public class SearchElement
{
// Display array elements
public void display(int[] arr, int size)
{
Console.Write("\n\n Array Elements \n [");
for (int i = 0; i < size; ++i)
{
Console.Write("  " + arr[i]);
}
Console.Write(" ]\n");
}
// Returns the location of first smallest element in given range
public int smallest(int[] arr, int low, int high)
{
for (int i = low + 1; i < high; ++i)
{
if (arr[low] > arr[i])
{
return i;
}
}
return low;
}
// Find min element in array
public int findMin(int[] arr, int low, int high)
{
int mid = (low + high) / 2;
if (low == high)
{
return low;
}
if (arr[low] >= arr[high])
{
if (arr[mid] > arr[high])
{
return findMin(arr, mid + 1, high);
}
if (arr[mid] < arr[high])
{
return findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{
// For exampe
// x        x         x
// 3  1  2  3   3  3  3
// or
// 3  3  3  3   1  2  3
// or (all duplicate)
// 3  3  3  3   3  3  3
return smallest(arr, low, high);
}
return low;
}
// 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)
{
if (size <= 0)
{
return;
}
int location = 0;
if (size > 1)
{
location = findMin(arr, 0, size - 1);
}
Console.Write(" Min Element " + arr[location] + " \n");
}
public static void Main(String[] args)
{
SearchElement work = new SearchElement();
// Defining sorted and rotated arrays of integer element
int[] arr1 = {
7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 6
};
int[] arr2 = {
15 , 17 , 3 , 4 , 5 , 7 , 8
};
int[] arr3 = {
3 , 3 , 5 , 0 , 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3
};
int[] arr4 = {
2 , 2 , 5 , 1 , 2
};
int[] arr5 = {
2 , 2 , 2 , 2 , 2 , -1 , 2 , 2
};
// Get the size
int size = arr1.Length;
// Case A
work.display(arr1, size);
work.minElement(arr1, size);
// Get the size
size = arr2.Length;
// Case B
work.display(arr2, size);
work.minElement(arr2, size);
// Get the size
size = arr3.Length;
// Case C
work.display(arr3, size);
work.minElement(arr3, size);
// Get the size
size = arr4.Length;
// Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
// Get the size
size = arr5.Length;
// Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
}
}``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1``````
``````<?php
/*
Php program
Find smallest element in sorted rotated array
*/
class SearchElement
{
// Display array elements
public  function display( \$arr, \$size)
{
echo "\n\n Array Elements \n [";
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$arr[\$i];
}
echo " ]\n";
}
// Returns the location of first smallest element in given range
public  function smallest( \$arr, \$low, \$high)
{
for (\$i = \$low + 1; \$i < \$high; ++\$i)
{
if (\$arr[\$low] > \$arr[\$i])
{
return \$i;
}
}
return \$low;
}
// Find min element in array
public  function findMin( & \$arr, \$low, \$high)
{
\$mid = intval((\$low + \$high) / 2);
if (\$low == \$high)
{
return \$low;
}
if (\$arr[\$low] >= \$arr[\$high])
{
if (\$arr[\$mid] > \$arr[\$high])
{
return \$this->findMin(\$arr, \$mid + 1, \$high);
}
if (\$arr[\$mid] < \$arr[\$high])
{
return \$this->findMin(\$arr, \$low, \$mid);
}
}
if (\$arr[\$mid] == \$arr[\$high])
{
// For exampe
// x        x         x
// 3  1  2  3   3  3  3
// or
// 3  3  3  3   1  2  3
// or (all duplicate)
// 3  3  3  3   3  3  3
return \$this->smallest(\$arr, \$low, \$high);
}
return \$low;
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated
public  function minElement( & \$arr, \$size)
{
if (\$size <= 0)
{
return;
}
\$location = 0;
if (\$size > 1)
{
\$location = \$this->findMin(\$arr, 0, \$size - 1);
}
echo " Min Element ". \$arr[\$location] ." \n";
}
}

function main()
{
\$work = new SearchElement();
// Defining sorted and rotated arrays of integer element
\$arr1 = array(7, 8, 9, 1, 2, 3, 4, 5, 6);
\$arr2 = array(15, 17, 3, 4, 5, 7, 8);
\$arr3 = array(3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3);
\$arr4 = array(2, 2, 5, 1, 2);
\$arr5 = array(2, 2, 2, 2, 2, -1, 2, 2);
// Get the size
\$size = count(\$arr1);
// Case A
\$work->display(\$arr1, \$size);
\$work->minElement(\$arr1, \$size);
// Get the size
\$size = count(\$arr2);
// Case B
\$work->display(\$arr2, \$size);
\$work->minElement(\$arr2, \$size);
// Get the size
\$size = count(\$arr3);
// Case C
\$work->display(\$arr3, \$size);
\$work->minElement(\$arr3, \$size);
// Get the size
\$size = count(\$arr4);
// Test Case D
\$work->display(\$arr4, \$size);
\$work->minElement(\$arr4, \$size);
// Get the size
\$size = count(\$arr5);
// Test Case E
\$work->display(\$arr5, \$size);
\$work->minElement(\$arr5, \$size);
}
main();``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1``````
``````/*
Node Js program
Find smallest element in sorted rotated array
*/
class SearchElement
{
// Display array elements
display(arr, size)
{
process.stdout.write("\n\n Array Elements \n [");
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + arr[i]);
}
process.stdout.write(" ]\n");
}
// Returns the location of first smallest element in given range
smallest(arr, low, high)
{
for (var i = low + 1; i < high; ++i)
{
if (arr[low] > arr[i])
{
return i;
}
}
return low;
}
// Find min element in array
findMin(arr, low, high)
{
var mid = parseInt((low + high) / 2);
if (low == high)
{
return low;
}
if (arr[low] >= arr[high])
{
if (arr[mid] > arr[high])
{
return this.findMin(arr, mid + 1, high);
}
if (arr[mid] < arr[high])
{
return this.findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{
// For exampe
// x        x         x
// 3  1  2  3   3  3  3
// or
// 3  3  3  3   1  2  3
// or (all duplicate)
// 3  3  3  3   3  3  3
return this.smallest(arr, low, high);
}
return low;
}
// Handles the request of finding min element in array
// We assume that given array is sorted and rotated
minElement(arr, size)
{
if (size <= 0)
{
return;
}
var location = 0;
if (size > 1)
{
location = this.findMin(arr, 0, size - 1);
}
process.stdout.write(" Min Element " + arr[location] + " \n");
}
}

function main()
{
var work = new SearchElement();
// Defining sorted and rotated arrays of integer element
var arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6];
var arr2 = [15, 17, 3, 4, 5, 7, 8];
var arr3 = [3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3];
var arr4 = [2, 2, 5, 1, 2];
var arr5 = [2, 2, 2, 2, 2, -1, 2, 2];
// Get the size
var size = arr1.length;
// Case A
work.display(arr1, size);
work.minElement(arr1, size);
// Get the size
size = arr2.length;
// Case B
work.display(arr2, size);
work.minElement(arr2, size);
// Get the size
size = arr3.length;
// Case C
work.display(arr3, size);
work.minElement(arr3, size);
// Get the size
size = arr4.length;
// Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
// Get the size
size = arr5.length;
// Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
}
main();``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1``````
``````#  Python 3 program
#  Find smallest element in sorted rotated array

class SearchElement :
#  Display array elements
def display(self, arr, size) :
print("\n\n Array Elements \n [", end = "")
i = 0
while (i < size) :
print("  ", arr[i], end = "")
i += 1

print(" ]")

#  Returns the location of first smallest element in given range
def smallest(self, arr, low, high) :
i = low + 1
while (i < high) :
if (arr[low] > arr[i]) :
return i

i += 1

return low

#  Find min element in array
def findMin(self, arr, low, high) :
mid = int((low + high) / 2)
if (low == high) :
return low

if (arr[low] >= arr[high]) :
if (arr[mid] > arr[high]) :
return self.findMin(arr, mid + 1, high)

if (arr[mid] < arr[high]) :
return self.findMin(arr, low, mid)

if (arr[mid] == arr[high]) :
#  For exampe
#  x        x         x
#  3  1  2  3   3  3  3
#  or
#  3  3  3  3   1  2  3
#  or (all duplicate)
#  3  3  3  3   3  3  3
return self.smallest(arr, low, high)

return low

#  Handles the request of finding min element in array
#  We assume that given array is sorted and rotated
def minElement(self, arr, size) :
if (size <= 0) :
return

location = 0
if (size > 1) :
location = self.findMin(arr, 0, size - 1)

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

def main() :
work = SearchElement()
#  Defining sorted and rotated arrays of integer element
arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]
arr2 = [15, 17, 3, 4, 5, 7, 8]
arr3 = [3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3]
arr4 = [2, 2, 5, 1, 2]
arr5 = [2, 2, 2, 2, 2, -1, 2, 2]
#  Get the size
size = len(arr1)
#  Case A
work.display(arr1, size)
work.minElement(arr1, size)
#  Get the size
size = len(arr2)
#  Case B
work.display(arr2, size)
work.minElement(arr2, size)
#  Get the size
size = len(arr3)
#  Case C
work.display(arr3, size)
work.minElement(arr3, size)
#  Get the size
size = len(arr4)
#  Test Case D
work.display(arr4, size)
work.minElement(arr4, size)
#  Get the size
size = len(arr5)
#  Test Case E
work.display(arr5, size)
work.minElement(arr5, size)

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

#### Output

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

Array Elements
[   15   17   3   4   5   7   8 ]
Min Element  3

Array Elements
[   3   3   5   0   2   3   3   3   3   3   3   3 ]
Min Element  0

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

Array Elements
[   2   2   2   2   2   -1   2   2 ]
Min Element  -1``````
``````#  Ruby program
#  Find smallest element in sorted rotated array

class SearchElement
#  Display array elements
def display(arr, size)
print("\n\n Array Elements \n [")
i = 0
while (i < size)
print("  ", arr[i])
i += 1
end

print(" ]\n")
end

#  Returns the location of first smallest element in given range
def smallest(arr, low, high)
i = low + 1
while (i < high)
if (arr[low] > arr[i])
return i
end

i += 1
end

return low
end

#  Find min element in array
def findMin(arr, low, high)
mid = (low + high) / 2
if (low == high)
return low
end

if (arr[low] >= arr[high])
if (arr[mid] > arr[high])
return self.findMin(arr, mid + 1, high)
end

if (arr[mid] < arr[high])
return self.findMin(arr, low, mid)
end

end

if (arr[mid] == arr[high])
#  For exampe
#  x        x         x
#  3  1  2  3   3  3  3
#  or
#  3  3  3  3   1  2  3
#  or (all duplicate)
#  3  3  3  3   3  3  3
return self.smallest(arr, low, high)
end

return low
end

#  Handles the request of finding min element in array
#  We assume that given array is sorted and rotated
def minElement(arr, size)
if (size <= 0)
return
end

location = 0
if (size > 1)
location = self.findMin(arr, 0, size - 1)
end

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

end

def main()
work = SearchElement.new()
#  Defining sorted and rotated arrays of integer element
arr1 = [7, 8, 9, 1, 2, 3, 4, 5, 6]
arr2 = [15, 17, 3, 4, 5, 7, 8]
arr3 = [3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3]
arr4 = [2, 2, 5, 1, 2]
arr5 = [2, 2, 2, 2, 2, -1, 2, 2]
#  Get the size
size = arr1.length
#  Case A
work.display(arr1, size)
work.minElement(arr1, size)
#  Get the size
size = arr2.length
#  Case B
work.display(arr2, size)
work.minElement(arr2, size)
#  Get the size
size = arr3.length
#  Case C
work.display(arr3, size)
work.minElement(arr3, size)
#  Get the size
size = arr4.length
#  Test Case D
work.display(arr4, size)
work.minElement(arr4, size)
#  Get the size
size = arr5.length
#  Test Case E
work.display(arr5, size)
work.minElement(arr5, size)
end

main()``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1
``````
``````/*
Scala program
Find smallest element in sorted rotated array
*/
class SearchElement
{
//  Display array elements
def display(arr: Array[Int], size: Int): Unit = {
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i < size)
{
print("  " + arr(i));
i += 1;
}
print(" ]\n");
}
//  Returns the location of first smallest element in given range
def smallest(arr: Array[Int], low: Int, high: Int): Int = {
var i: Int = low + 1;
while (i < high)
{
if (arr(low) > arr(i))
{
return i;
}
i += 1;
}
return low;
}
//  Find min element in array
def findMin(arr: Array[Int], low: Int, high: Int): Int = {
var mid: Int = ((low + high) / 2).toInt;
if (low == high)
{
return low;
}
if (arr(low) >= arr(high))
{
if (arr(mid) > arr(high))
{
return this.findMin(arr, mid + 1, high);
}
if (arr(mid) < arr(high))
{
return this.findMin(arr, low, mid);
}
}
if (arr(mid) == arr(high))
{
//  For exampe
//  x        x         x
//  3  1  2  3   3  3  3
//  or
//  3  3  3  3   1  2  3
//  or (all duplicate)
//  3  3  3  3   3  3  3
return this.smallest(arr, low, high);
}
return low;
}
//  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 = {
if (size <= 0)
{
return;
}
var location: Int = 0;
if (size > 1)
{
location = this.findMin(arr, 0, size - 1);
}
print(" Min Element " + arr(location) + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var work: SearchElement = new SearchElement();
//  Defining sorted and rotated arrays of integer element
var arr1: Array[Int] = Array(7, 8, 9, 1, 2, 3, 4, 5, 6);
var arr2: Array[Int] = Array(15, 17, 3, 4, 5, 7, 8);
var arr3: Array[Int] = Array(3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3);
var arr4: Array[Int] = Array(2, 2, 5, 1, 2);
var arr5: Array[Int] = Array(2, 2, 2, 2, 2, -1, 2, 2);
//  Get the size
var size: Int = arr1.length;
//  Case A
work.display(arr1, size);
work.minElement(arr1, size);
//  Get the size
size = arr2.length;
//  Case B
work.display(arr2, size);
work.minElement(arr2, size);
//  Get the size
size = arr3.length;
//  Case C
work.display(arr3, size);
work.minElement(arr3, size);
//  Get the size
size = arr4.length;
//  Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
//  Get the size
size = arr5.length;
//  Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
}
}``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

Array Elements
[  2  2  2  2  2  -1  2  2 ]
Min Element -1``````
``````/*
Swift 4 program
Find smallest element in sorted rotated array
*/
class SearchElement
{
//  Display array elements
func display(_ arr: [Int], _ size: Int)
{
print("\n\n Array Elements \n [", terminator: "");
var i: Int = 0;
while (i < size)
{
print("  ", arr[i], terminator: "");
i += 1;
}
print(" ]");
}
//  Returns the location of first smallest element in given range
func smallest(_ arr: [Int], _ low: Int, _ high: Int)->Int
{
var i: Int = low + 1;
while (i < high)
{
if (arr[low] > arr[i])
{
return i;
}
i += 1;
}
return low;
}
//  Find min element in array
func findMin(_ arr: [Int], _ low: Int, _ high: Int)->Int
{
let mid: Int = (low + high) / 2;
if (low == high)
{
return low;
}
if (arr[low] >= arr[high])
{
if (arr[mid] > arr[high])
{
return self.findMin(arr, mid + 1, high);
}
if (arr[mid] < arr[high])
{
return self.findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{
//  For exampe
//  x        x         x
//  3  1  2  3   3  3  3
//  or
//  3  3  3  3   1  2  3
//  or (all duplicate)
//  3  3  3  3   3  3  3
return self.smallest(arr, low, high);
}
return low;
}
//  Handles the request of finding min element in array
//  We assume that given array is sorted and rotated
func minElement(_ arr: [Int], _ size: Int)
{
if (size <= 0)
{
return;
}
var location: Int = 0;
if (size > 1)
{
location = self.findMin(arr, 0, size - 1);
}
print(" Min Element ", arr[location]," ");
}
}
func main()
{
let work: SearchElement = SearchElement();
//  Defining sorted and rotated arrays of integer element
let arr1: [Int] = [7, 8, 9, 1, 2, 3, 4, 5, 6];
let arr2: [Int] = [15, 17, 3, 4, 5, 7, 8];
let arr3: [Int] = [3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3];
let arr4: [Int] = [2, 2, 5, 1, 2];
let arr5: [Int] = [2, 2, 2, 2, 2, -1, 2, 2];
//  Get the size
var size: Int = arr1.count;
//  Case A
work.display(arr1, size);
work.minElement(arr1, size);
//  Get the size
size = arr2.count;
//  Case B
work.display(arr2, size);
work.minElement(arr2, size);
//  Get the size
size = arr3.count;
//  Case C
work.display(arr3, size);
work.minElement(arr3, size);
//  Get the size
size = arr4.count;
//  Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
//  Get the size
size = arr5.count;
//  Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
}
main();``````

#### Output

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

Array Elements
[   15   17   3   4   5   7   8 ]
Min Element  3

Array Elements
[   3   3   5   0   2   3   3   3   3   3   3   3 ]
Min Element  0

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

Array Elements
[   2   2   2   2   2   -1   2   2 ]
Min Element  -1``````
``````/*
Kotlin program
Find smallest element in sorted rotated array
*/
class SearchElement
{
//  Display array elements
fun display(arr: Array<Int>, size: Int): Unit
{
print("\n\n Array Elements \n [");
var i: Int = 0;
while (i<size)
{
print("  " + arr[i]);
i += 1;
}
print(" ]\n");
}
//  Returns the location of first smallest element in given range
fun smallest(arr: Array<Int>, low: Int, high: Int): Int
{
var i: Int = low + 1;
while (i<high)
{
if (arr[low]>arr[i])
{
return i;
}
i += 1;
}
return low;
}
//  Find min element in array
fun findMin(arr: Array<Int>, low: Int, high: Int): Int
{
var mid: Int = (low + high) / 2;
if (low == high)
{
return low;
}
if (arr[low]>= arr[high])
{
if (arr[mid]>arr[high])
{
return this.findMin(arr, mid + 1, high);
}
if (arr[mid]<arr[high])
{
return this.findMin(arr, low, mid);
}
}
if (arr[mid] == arr[high])
{

//  For exampe
//  x        x         x
//  3  1  2  3   3  3  3
//  or
//  3  3  3  3   1  2  3
//  or (all duplicate)
//  3  3  3  3   3  3  3
return this.smallest(arr, low, high);
}
return low;
}
//  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
{
if (size <= 0)
{
return;
}
var location: Int = 0;
if (size > 1)
{
location = this.findMin(arr, 0, size - 1);
}
print(" Min Element " + arr[location] + " \n");
}
}
fun main(args: Array<String>): Unit
{
var work: SearchElement = SearchElement();
//  Defining sorted and rotated arrays of integer element
var arr1: Array<Int> = arrayOf(7, 8, 9, 1, 2, 3, 4, 5, 6);
var arr2: Array<Int> = arrayOf(15, 17, 3, 4, 5, 7, 8);
var arr3: Array<Int> = arrayOf(3, 3, 5, 0, 2, 3, 3, 3, 3, 3, 3, 3);
var arr4: Array<Int> = arrayOf(2, 2, 5, 1, 2);
var arr5: Array<Int> = arrayOf(2, 2, 2, 2, 2, -1, 2, 2);
//  Get the size
var size: Int = arr1.count();
//  Case A
work.display(arr1, size);
work.minElement(arr1, size);
//  Get the size
size = arr2.count();
//  Case B
work.display(arr2, size);
work.minElement(arr2, size);
//  Get the size
size = arr3.count();
//  Case C
work.display(arr3, size);
work.minElement(arr3, size);
//  Get the size
size = arr4.count();
//  Test Case D
work.display(arr4, size);
work.minElement(arr4, size);
//  Get the size
size = arr5.count();
//  Test Case E
work.display(arr5, size);
work.minElement(arr5, size);
}``````

#### Output

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

Array Elements
[  15  17  3  4  5  7  8 ]
Min Element 3

Array Elements
[  3  3  5  0  2  3  3  3  3  3  3  3 ]
Min Element 0

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

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

## 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.

Categories
Relative Post