Example: {3, 4, 5, 6, 7, 1, 2} output: 1

Algorithm:

This problem can be easily solved in O(n) time complexity buy traversing the

whole array and check for minimum element.

Here we are using a different solution which takes O(Log n)

Let us look at this approach, we are using a modified version of Binary Search Tree algorithm.

Thanks Dheeraj for sharing Question and Code for this .

Code:

#include<iostream>

using namespace std;

int BST(int A[],int low,int high){

int mid=low+(high-low)/2;

if ( mid == high ) return A[mid]; //if size of sub array is 1

if(mid < high && mid > low && A[mid] < A[mid + 1] && A[mid -1] > A[mid] )

return A[mid];

//compare value of mid + 1,mid, mid-1 if they exist

if(A[mid] > A[high]) {

if(A[mid + 1] < A[mid]) return A[mid + 1];

else return BST(A, mid + 1, high); //check in right sub array

}

else

{

if(A[mid] < A[mid – 1]) return A[mid];

else return BST(A , low , mid – 1); //check in left sub array

}

}

int main()

{

int A[]={3,4,5,6,7,1,2};

int n= sizeof(A)/sizeof(A[0]);

cout<<BST(A,0,n-1)<<endl;

}