# Find the minimum element in a sorted and rotated array

We are given a sorted array that is rotated by some index. We have to find the minimum element in the rotated array.

For example the given sorted array is [1, 2, 3, 4, 5, 6]. Suppose it is rotated left by 3.

The sorted rotated array will be [4, 5, 6, 1, 2, 3]

Here we have to find the minimum element which is 1.

Ideally we can search the minimum element from this array by checking each element and comparing it against the minimum element. But this will be a linear search and will take O(n) time if the element is at the last index

Since the array is sorted, we can do better in searching the min element by using a binary search.

Binary search is a search mechanism where we divide the array and look for the array in that part of array, essentially dividing our search size into half. But, here since the array is also rotated, we need to check for few additional conditions since the minimum element is no longer at the first position

#### Understand binary search for sorted and rotated array

When we closely look at the sorted and rotated array, there are 3 different cases that are possible.

And it does not matter whether the array is right rotated or left rotated

##### Case 1: Array is not rotated at all

- Example: int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}
- In this case the min element is at the first position and the max element is at the last position
- arr[0] < arr[arr.length-1] holds true in this case

##### Case 2: Minimum element is to the right side of middle element

- Example: int[] arr = {4, 5, 6, 7, 8, 9, 1, 2, 3}
- In this case, the element in the middle is greater than the leftmost and rightmost element
- Element 8 is greater then 4 and 3
- To do a binary search in the right side of mid element 8, we can compare element at mid position with element at last position
- array[mid] > array[last] holds true in this case

##### Case 3: Minimum element is to the left side of middle element

- Example: int[] arr = {7, 8, 9, 1, 2, 3, 4, 5, 6}
- In this case, the element in the middle is less than the leftmost and rightmost element in the array
- Element 2 is less then 7 and 6 and the min element falls to the left of 2, so we want to search in the left side of mid element
- In this case if you notice, the condition for case 2 array[mid] > array[right] becomes false
- This means when the condition for case 2 is false, we can safely assume the min element will be on the left side of mid element

#### Algorithm

- Initialize the first, last element
- loop while first is less than last element
- Initialize mid element
- If the mid element is greater than last element then search in right half
- Else search in left half

- return first element

#### Code

```
#Java Code
class FindMinInSortedRotatedArray{
public static int findMin(int array[])
{
int first = 0;
int last = array.length - 1;
while(first < last)
{
int mid = first + (last - first) / 2;
if(array[mid] > array[last]){
first = mid + 1;
}
else{
last = mid;
}
}
return array[first];
}
public static void main(String[] args)
{
int array[] = {7, 8, 1, 2, 3, 4, 5, 6};
FindMinInSortedRotatedArray fm = new FindMinInSortedRotatedArray();
int n = fm.findMin(array);
System.out.println("Minimum element in the sorted and rotated array is : " + n);
}
}
```

##### Output

Minimum element in the sorted and rotated array is : 1