## Wednesday, May 4, 2022

### Question 13 : Find minimum element in a sorted and rotated array

You are given an sorted and rotated array as below::

``````int arr[]={16,19,21,25,3,5,8,10};
Minimum element in the array : 3``````

If you note that array is sorted and rotated. You need to I an element in the above array in o(log n) time complexity.

#### Solution:

You can use a variant of binary search algorithm to solve the above problem. You can use a property that if you divide the array into two sorted sub-arrays ({16,19,21,25},{3,5,8,10} ), one will be sorted and the other will have a minimum element

#### Algorithm:

• Compute mid i.e low+high/2.
• Check if a[mid…high] is sorted
• Minimum lies in left part, so low=mid+1;
• Else
• Minimum lies in right part, so high=mid

### Java program to find minimum element in a sorted and rotated array :

Create a class named

MinimumElementSortedAndRotatedArrayMain.java.:
``````public class MinimumElementSortedAndRotatedArrayMain {

public static void main(String[] args) {
int arr[] = {
16,
19,
21,
25,
3,
5,
8,
10
};
System.out.println("Minimum element in the array : " + findMinimumElementRotatedSortedArray(arr, 0, arr.length - 1, 5));

}

public static int findMinimumElementRotatedSortedArray(int[] arr, int low, int high, int number) {
int mid;

while (low < high) {
mid = low + ((high - low) / 2);

if (arr[mid] > arr[high]) {
low = mid + 1;
} else {
high = mid;
}
}
return arr[low];
}
}``````

When you run above program, you will get below output::

``````Minimum element in the array : 3
``````

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS