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