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) ;
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )