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 : 1Better 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
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.
New Comment