Find the minimum element in a sorted and rotated array
A sorted array is rotated at some unknown point, find the minimum element in it.
Following solution assumes that all elements are distinct.
Examples
Input: {5, 6, 1, 2, 3, 4} Output: 1 Input: {1, 2, 3, 4} Output: 1 Input: {2, 1} Output: 1
A simple solution is to traverse the complete array and find minimum. This solution requires Θ(n) time.
We can do it in O(Logn) using Binary Search. If we take a closer look at above examples, we can easily figure out following pattern:
 The minimum element is the only element whose previous is greater than it. If there is no previous element element, then there is no rotation (first element is minimum). We check this condition for middle element by comparing it with (mid1)’th and (mid+1)’th elements.
 If minimum element is not at middle (neither mid nor mid + 1), then minimum element lies in either left half or right half.
 If middle element is smaller than last element, then the minimum element lies in left half
 Else minimum element lies in right half.
We strongly recommend you to try it yourself before seeing the following implementation.
 C/C++

// C program to find minimum element in a sorted and rotated array
#include <stdio.h>
int
findMin(
int
arr[],
int
low,
int
high)
{
// This condition is needed to handle the case when array is not
// rotated at all
if
(high < low)
return
arr[0];
// If there is only one element left
if
(high == low)
return
arr[low];
// Find mid
int
mid = low + (high  low)/2;
/*(low + high)/2;*/
// Check if element (mid+1) is minimum element. Consider
// the cases like {3, 4, 5, 1, 2}
if
(mid < high && arr[mid+1] < arr[mid])
return
arr[mid+1];
// Check if mid itself is minimum element
if
(mid > low && arr[mid] < arr[mid  1])
return
arr[mid];
// Decide whether we need to go to left half or right half
if
(arr[high] > arr[mid])
return
findMin(arr, low, mid1);
return
findMin(arr, mid+1, high);
}
// Driver program to test above functions
int
main()
{
int
arr1[] = {5, 6, 1, 2, 3, 4};
int
n1 =
sizeof
(arr1)/
sizeof
(arr1[0]);
printf
(
"The minimum element is %dn"
, findMin(arr1, 0, n11));
int
arr2[] = {1, 2, 3, 4};
int
n2 =
sizeof
(arr2)/
sizeof
(arr2[0]);
printf
(
"The minimum element is %dn"
, findMin(arr2, 0, n21));
int
arr3[] = {1};
int
n3 =
sizeof
(arr3)/
sizeof
(arr3[0]);
printf
(
"The minimum element is %dn"
, findMin(arr3, 0, n31));
int
arr4[] = {1, 2};
int
n4 =
sizeof
(arr4)/
sizeof
(arr4[0]);
printf
(
"The minimum element is %dn"
, findMin(arr4, 0, n41));
int
arr5[] = {2, 1};
int
n5 =
sizeof
(arr5)/
sizeof
(arr5[0]);
printf
(
"The minimum element is %dn"
, findMin(arr5, 0, n51));
int
arr6[] = {5, 6, 7, 1, 2, 3, 4};
int
n6 =
sizeof
(arr6)/
sizeof
(arr6[0]);
printf
(
"The minimum element is %dn"
, findMin(arr6, 0, n61));
int
arr7[] = {1, 2, 3, 4, 5, 6, 7};
int
n7 =
sizeof
(arr7)/
sizeof
(arr7[0]);
printf
(
"The minimum element is %dn"
, findMin(arr7, 0, n71));
int
arr8[] = {2, 3, 4, 5, 6, 7, 8, 1};
int
n8 =
sizeof
(arr8)/
sizeof
(arr8[0]);
printf
(
"The minimum element is %dn"
, findMin(arr8, 0, n81));
int
arr9[] = {3, 4, 5, 1, 2};
int
n9 =
sizeof
(arr9)/
sizeof
(arr9[0]);
printf
(
"The minimum element is %dn"
, findMin(arr9, 0, n91));
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
How to handle duplicates?
It turned out that duplicates can’t be handled in O(Logn) time in all cases. The special cases that cause problems are like {2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 2} and {2, 2, 2, 0, 2, 2, 2, 2, 2, 2, 2, 2}. It doesn’t look possible to go to left half or right half by doing constant number of comparisons at the middle. So the problem with repetition can be solved in O(n) worst case.
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide