If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.
In this post, we will see how to find minimum element in sorted and rotated array.
Problem:
You are given an sorted and rotated array as below:
int arr[]={16,19,21,25,3,5,8,10};
If you note that array is sorted and rotated. You need to find minimum element in above array in o(log n) time complexity. You can assume that duplicates are not allowed in the array.
Solution:
You can use variant of binary search algorithm to solve above problem. You can use a property that if you divide array into two sorted sub arrays ({16,19,21,25},{3,5,8,10} ), one will be sorted and other will have 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.
package org.arpit.java2blog;
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 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
