Problem: Find the minimum element in a sorted and rotated array if duplicates are allowed:
Example: { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2} output: 0
Algorithm:
Example: { 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2} output: 0
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 also take O(n) time complexity in worst case but it is more optimized.
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 .
#include<iostream>
using namespace std;
int mini(int a,int b)
{
if(a<b) return a;
else return b;
}
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[high])
{
if(A[mid] < A[mid – 1]) return A[mid];
else return BST(A , low , mid – 1); //check in left sub array
}
else if(A[mid]==A[high])
{
return min(BST(A,low,mid–1),BST(A,mid+1,high));// check for minimum in both left and right sub array and choose minimum of them
}
}
int main()
{
int A[]={2, 2, 2, 2, 2, 2, 2, 2,0, 0, 1, 1, 2};
int n= sizeof(A)/sizeof(A[0]);
cout<<BST(A,0,n–1)<<endl;
}