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

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

 

 Share This

You may also like

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