In this tutorial, I am going to discuss a very interesting problem find minimum in rotated sorted array.
Given an array which is sorted in ascending order is rotated at some unknown point. Write a code to find the minimum element in a sorted and rotated array.
You may assume no duplicate exists in the array.
For example:
Example 1:
Input: [6, 7, 8, 1, 2]
Output: 1
The minimum element in this sorted and rotated array is 1.
Example 2:
Input: [8, 9, 10, 1, 0, 1, 2]
Output: 0
In this example, the minimum element is 0.
In this problem, the array is rotated between 1 to n times where n is the length of an array. How do we find the minimum in sorted rotated array.
In this tutorial, I am going to discuss multiple approaches and it’s java code to solve this problem.
Find Minimum Element in a Sorted and Rotated Array using Linear Search
The simplest solution is to traverse complete array to find the minimum element.
Declare one variable and assign the element present at 0th index. Then, run a loop from 1 to n-1. Then, for each index value compare the current index value with the variable value. If current index value is less than the variable value then reassigned the minimum value.
The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/* Find minimum in rotated sorted array using Linear Search */ public class MinimumInSortedRotated { public static int findMinUsingLinearSearch(int[] arr) { //Assign value present at array index 0 int min = arr[0]; //Traverse an array for(int i = 1; i < arr.length; i++) { /* If any value is less than the assigned value, then reassigned the minimum value. */ if(min > arr[i]) { min = arr[i]; } } return min; } public static void main(String[] args) { int arr[] = {6, 7, 8, 1, 2}; int result = findMinUsingLinearSearch(arr); System.out.println(result); } } |
Find Minimum in Rotated Sorted Array using Binary Search
In our previous example, we have traversed complete array to solve this problem. How we can improve our solution?
In this example, I am going to explain how we can solve this problem using binary search in O(logn) time complexity.
If you are not familiar with the binary search algorithm then check my previous tutorials.
Binary search using recursion in java
The array is sorted and rotated. So, It is clear that the minimum element in this array is the only element whose previous element is greater than it. If the array is sorted then the minimum element is the element present at 0th index.
In Binary Search, we first calculate the mid. To find the minimum element we can compare mid with mid-1 and mid+1 element. If it is not found at mid then the minimum element lies either in left or right half.
i) If the middle element is smaller than the last element, then the minimum element lies in the left half.
ii) Else minimum element lies in the right half.
Search in Rotated Sorted Array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
/* Find minimum in a rotated sorted array using binary search */ public class MinElementInRotatedSortedArray { public static int findMin(int[] arr) { // If the array has only one element, arr = {1} if(arr.length == 1) { return arr[0]; } int start = 0; int end = arr.length - 1; /* If the array is sorted, arr = {1, 2, 3, 4}, then the minimum element is the element present at index 0. */ if(arr[0] < arr[end]) { return arr[0]; } while (start <= end) { int mid = (start + end)/2; if(start < mid && arr[mid] < arr[mid-1]) { return arr[mid]; } else if (end > mid && arr[mid+1] < arr[mid]) { return arr[mid+1]; } else if (arr[end] > arr[mid]) { end = mid-1; } else { start = mid + 1; } } return -1; } public static void main(String[] args) { //Test inputs //int arr[] = { 7, 8, 9, 10, 1, 2, 3, 5, 6}; int arr[] = {5, 6, 1, 2, 3, 4}; //int arr[] = {1, 2, 3, 4}; //int arr[] = {2, 1}; //int arr[] = {1} //int arr[] = {11, 2, 3, 4, 5, 6, 7, 8}; int result = findMin(arr); System.out.println(result); } } |
In this video tutorial, I have discussed the multiple approaches to solve this problem.
