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

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest