How to handle duplicates?
The above approach in the worst case(If all the elements are the same) takes O(N).
Below is the code to handle duplicates in O(log n) time.
- C++
// C++ program to find minimum element in a sorted
// and rotated array contacting duplicate elements.
#include <bits/stdc++.h>
using
namespace
std;
// Function to find minimum element
int
findMin(
int
arr[],
int
low,
int
high)
{
`` while
(low < high)
`` {
`` int
mid = low + (high - low)/2;
`` if
(arr[mid] == arr[high])
`` high--;
`` else
if
(arr[mid] > arr[high])
`` low = mid + 1;
`` else
`` high = mid;
`` }
`` return
arr[high];
}
// Driver code
int
main()
{
`` int
arr1[] = {5, 6, 1, 2, 3, 4};
`` int
n1 =
sizeof
(arr1)/
sizeof
(arr1[0]);
`` cout <<
"The minimum element is "
<< findMin(arr1, 0, n1-1) << endl;
``
`` int
arr2[] = {1, 2, 3, 4};
`` int
n2 =
sizeof
(arr2)/
sizeof
(arr2[0]);
`` cout <<
"The minimum element is "
<< findMin(arr2, 0, n2-1) << endl;
``
`` int
arr3[] = {1};
`` int
n3 =
sizeof
(arr3)/
sizeof
(arr3[0]);
`` cout<<
"The minimum element is "
<<findMin(arr3, 0, n3-1)<<endl;
``
`` int
arr4[] = {1, 2};
`` int
n4 =
sizeof
(arr4)/
sizeof
(arr4[0]);
`` cout<<
"The minimum element is "
<<findMin(arr4, 0, n4-1)<<endl;
``
`` int
arr5[] = {2, 1};
`` int
n5 =
sizeof
(arr5)/
sizeof
(arr5[0]);
`` cout<<
"The minimum element is "
<<findMin(arr5, 0, n5-1)<<endl;
``
`` int
arr6[] = {5, 6, 7, 1, 2, 3, 4};
`` int
n6 =
sizeof
(arr6)/
sizeof
(arr6[0]);
`` cout<<
"The minimum element is "
<<findMin(arr6, 0, n6-1)<<endl;
``
`` int
arr7[] = {1, 2, 3, 4, 5, 6, 7};
`` int
n7 =
sizeof
(arr7)/
sizeof
(arr7[0]);
`` cout <<
"The minimum element is "
<< findMin(arr7, 0, n7-1) << endl;
``
`` int
arr8[] = {2, 3, 4, 5, 6, 7, 8, 1};
`` int
n8 =
sizeof
(arr8)/
sizeof
(arr8[0]);
`` cout <<
"The minimum element is "
<< findMin(arr8, 0, n8-1) << endl;
``
`` int
arr9[] = {3, 4, 5, 1, 2};
`` int
n9 =
sizeof
(arr9)/
sizeof
(arr9[0]);
`` cout <<
"The minimum element is "
<< findMin(arr9, 0, n9-1) << endl;
``
`` return
0;
}
Output:
The minimum element is 1 The minimum element is 1 The minimum element is 1 The minimum element is 1 The minimum element is 1 The minimum element is 1 The minimum element is 1 The minimum element is 1 The minimum element is 1