# Element in a sorted and rotated array

A sorted array is rotated at some unknown point, find the minimum element in it.
The 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 a minimum. This solution requires O(n) time.
We can do it in O(Logn) using Binary Search. If we take a closer look at the above examples, we can easily figure out the following pattern:

• The minimum element is the only element whose previous is greater than it. If there is no previous element, then there is no rotation (the first element is minimum). We check this condition for the middle element by comparing it with (mid-1)’th and (mid+1)’th elements.
• If the minimum element is not at the middle (neither mid nor mid + 1), then the minimum element lies in either the left half or right half.
1. If the middle element is smaller than the last element, then the minimum element lies in the left half
2. Else minimum element lies in the 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, mid-1);`

`` `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 %d\n"` `, findMin(arr1, 0, n1-1));`

`` `int` `arr2[] = {1, 2, 3, 4};`

`` `int` `n2 = ` `sizeof` `(arr2)/` `sizeof` `(arr2[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr2, 0, n2-1));`

`` `int` `arr3[] = {1};`

`` `int` `n3 = ` `sizeof` `(arr3)/` `sizeof` `(arr3[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr3, 0, n3-1));`

`` `int` `arr4[] = {1, 2};`

`` `int` `n4 = ` `sizeof` `(arr4)/` `sizeof` `(arr4[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr4, 0, n4-1));`

`` `int` `arr5[] = {2, 1};`

`` `int` `n5 = ` `sizeof` `(arr5)/` `sizeof` `(arr5[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr5, 0, n5-1));`

`` `int` `arr6[] = {5, 6, 7, 1, 2, 3, 4};`

`` `int` `n6 = ` `sizeof` `(arr6)/` `sizeof` `(arr6[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr6, 0, n6-1));`

`` `int` `arr7[] = {1, 2, 3, 4, 5, 6, 7};`

`` `int` `n7 = ` `sizeof` `(arr7)/` `sizeof` `(arr7[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr7, 0, n7-1));`

`` `int` `arr8[] = {2, 3, 4, 5, 6, 7, 8, 1};`

`` `int` `n8 = ` `sizeof` `(arr8)/` `sizeof` `(arr8[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr8, 0, n8-1));`

`` `int` `arr9[] = {3, 4, 5, 1, 2};`

`` `int` `n9 = ` `sizeof` `(arr9)/` `sizeof` `(arr9[0]);`

`` `printf` `(` `"The minimum element is %d\n"` `, findMin(arr9, 0, n9-1));`

`` `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?

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