find minimum element in a sorted and rotated array

Previous
Next

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:

Previous
Next

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.

Add Comment

Join Our News Letter - Stay Updated

Subscribe to Awesome Java Content.
You can like our facebook page Java2blog