Minimum element in a sorted and rotated array
PROBLEM :
A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it.
Expected Time Complexity: O(Log n)
Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array.
The second line of each test case contains N space separated integers denoting array elements.
Output:
Corresponding to each test case, in a new line, print the minimum element in the array.
Constraints:
1 = T = 100
1 = N = 500
1 = A[i] = 1000
Example:
Input
1
5
4 5 1 2 3
Output
1
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
#define max 500
int Minimum_element(int [],int ,int ) ;
int main()
{
int t ,no ,i ;
int arr[max] ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>arr[i] ;
cout<<Minimum_element(arr,0,no-1)<<endl ;
}
return 0;
}
int Minimum_element(int arr[],int start,int end)
{
int mid ;
if(start==end)
return arr[start] ;
mid=(start+end)/2 ;
if(mid<end&&arr[mid]>arr[mid+1])
return arr[mid+1] ;
if(mid>start&&arr[mid]<arr[mid-1])
return arr[mid] ;
if(arr[mid]>arr[end])
return Minimum_element(arr,mid+1,end) ;
else
return Minimum_element(arr,start,mid-1) ;
}
---------------------------------------------------------------------------------
A sorted array A[ ] with distinct elements is rotated at some unknown point, the task is to find the minimum element in it.
Expected Time Complexity: O(Log n)
Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consist of two lines. The first line of each test case consists of an integer N, where N is the size of array.
The second line of each test case contains N space separated integers denoting array elements.
Output:
Corresponding to each test case, in a new line, print the minimum element in the array.
Constraints:
1 = T = 100
1 = N = 500
1 = A[i] = 1000
Example:
Input
1
5
4 5 1 2 3
Output
1
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
using namespace std;
#define max 500
int Minimum_element(int [],int ,int ) ;
int main()
{
int t ,no ,i ;
int arr[max] ;
cin>>t ;
while(t--)
{
cin>>no ;
for(i=0;i<no;i++)
cin>>arr[i] ;
cout<<Minimum_element(arr,0,no-1)<<endl ;
}
return 0;
}
int Minimum_element(int arr[],int start,int end)
{
int mid ;
if(start==end)
return arr[start] ;
mid=(start+end)/2 ;
if(mid<end&&arr[mid]>arr[mid+1])
return arr[mid+1] ;
if(mid>start&&arr[mid]<arr[mid-1])
return arr[mid] ;
if(arr[mid]>arr[end])
return Minimum_element(arr,mid+1,end) ;
else
return Minimum_element(arr,start,mid-1) ;
}
---------------------------------------------------------------------------------
Comments
Post a Comment