# Find Minimum in sorted rotated array

In post find element in sorted rotated array, we discussed an algorithm based on binary search, to find a given key in sorted rotated array. Problem today is bit different, there is no key to find first of all. Ask of problem is to **find minimum in sorted rotated array**.

To understand problem, first let’s understand what is sorted array and then what is sorted rotated array.

An array is called sorted where for all i and j such that i < j, A[i] <= A[j]. A rotation happens when last element of array is push at the start and all elements of array move right by one position. This is called as rotation by 1. If new last element is also pushed to start again, all elements are moved to right, it’s rotation by 2 and so on.

Find minimum in sorted rotated array problem is asked during telephonic or online coding rounds of companies like Microsoft or Amazon.

## Find minimum in sorted rotated array : Thought process

As always, first come up with a brute force solution without worrying about any optimizations as of now. Simplest way would be to scan through array and keep track of minimum. Complexity of this method is O(N), however, what is the fun if we do it in O(N) time complexity ?

In brute force solution, we did not use the fact that array is sorted and then rotated. Let’s forget about rotation and concentrate only in sorted part.

What is minimum element in sorted array? Obviously, it is the first element of array. We see that all the elements on right side of minimum elements are greater than minimum.

What will happen if start rotating array now, is the condition that all the elements on right of minimum element are greater than it still hold? Yes, it does. Either there will be no element on right side of minimum or the will be definitely greater than it.

*Array could have been in two ways : It is rotated more than half or it is rotated less than half.*## Minimum in sorted rotated array : Algorithm

- Find mid = start + (end- start) /2
- See if mid is minimum element i.e is A[mid] < A[mid-1] and A[mid] < A[mid+1]. If yes, return mid
- Else if A[mid] > A[end]:
- Array is rotated more than half, minimum should be on right subarray
- Continue with subarray with start = mid+1

- Else if A[mid] < A[end]:
- Array is rotated less than half, minimum should be on left subarray
- Continue with subarray with end = mid-1

### Minimum in sorted rotated array implementation

package com.company; /** * Created by sangar on 22.3.18. */ public class SortedRotatedArray { public static int findMinimumIterative(int[] input, int start, int end) { while (start < end) { int mid = start + (end - start) / 2; if (mid == 0 || (input[mid] <= input[mid+1] && input[mid] < input[mid-1])) return mid; else if (input[mid] > input[mid]) { /* Array is rotated more than half, hence minimum should be in right sub-array */ start = mid + 1; } else { /* Array is rotated less than half, hence minimum should be in left sub-array */ end = mid - 1; } } return start; } public static void main(String[] args) { int[] input = {10,11,15,17,3,3,3,3,3,3}; int index = findMinimumIterative(input,0, input.length-1); System.out.print(index == -1 ? "Element not found" : "Element found at : " + index); } }

Recursive implementation of same function

package com.company; /** * Created by sangar on 22.3.18. */ public class SortedRotatedArray { public static int findMinimumRecursive(int[] input, int start, int end){ if(start < end){ int mid = start + (end - start) / 2; if(mid == 0 || (input[mid] < input[mid-1] && input[mid] <= input[mid+1] ) ) return mid; else if(input[mid] > input[end]){ /* Array is rotated more than half and hence, search in right subarray */ return findMinimumRecursive(input, mid+1, end); }else { return findMinimumRecursive(input, start, mid - 1); } } return start; } public static void main(String[] args) { int[] input = {3,10,11,15,17,18,19,20}; int index = findMinimumRecursive(input,0, input.length-1); System.out.print(index == -1 ? "Element not found" : "Element found at : " + index); } }

Complexity of algorithm to find minimum in sorted rotated array is O(log N), with recursive implementation having implicit space complexity of O(log N).

What did we learn from this problem?

First learning is to always go for brute force method. Second, try to draw the effect of any additional operations which are done on original array. In sorted rotated array, try to have rotation one by one and see what impact it has on minimum element? Try to classify individual class and design your algorithm. In this problem, we identify that based on how many times array is rotated, minimum can be in right or left subarray from middle and that gave idea for discarding half of the array.

Please share if there is something wrong or missing, or any improvement we can do. Please reach out to us if you are willing to share your knowledge and contribute to learning process of others.