find minimum element in a sorted and rotated array

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:

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.
When you run above program, you will get below output:

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *