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