Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach

«
»
This is a Java Program to find minimum element of a rotated sorted array. The following program uses a binary search approach to find the minimum element of a rotated sorted array. Time complexity is O (log n)

Here is the source code of the Java program to find minimum element of a rotated sorted array. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /*
  2.  * Java Program to Find the Minimum element of a rotated 
  3.  * sorted Array using Binary Search approach
  4.  */
  5.  
  6. import java.util.Scanner;
  7.  
  8. public class MinimumElementInRotatedSortedArray
  9. {
  10.     public static void main(String[] args) 
  11.     {
  12.         Scanner scan = new Scanner(System.in);
  13.         System.out.println("Enter number of elements in array");
  14.         int N = scan.nextInt();
  15.         int[] arr = new int[ N ];
  16.         /* Accept N elements */
  17.         System.out.println("Enter "+ N +" elements of rotated sorted array");
  18.         for (int i = 0; i < N; i++)
  19.             arr[i] = scan.nextInt();
  20.         System.out.println("Minimum element = "+ min(arr));
  21.     }
  22.     public static int min(int[] arr)
  23.     {
  24.         return min(arr, 0, arr.length - 1);
  25.     }
  26.     public static int min(int[] arr, int low, int high)
  27.     {
  28.         if (high < low)  
  29.             return arr[0];        
  30.         if (high == low) 
  31.             return arr[low];
  32.         /* Calculate mid position */
  33.         int mid = (high + low)/2;
  34.         if (mid < high && arr[mid + 1] < arr[mid])
  35.            return arr[mid + 1];            
  36.         if (mid > low && arr[mid] < arr[mid - 1])
  37.            return arr[mid];
  38.         /* recursively find min */   
  39.         if (arr[high] > arr[mid])
  40.            return min(arr, low, mid - 1);
  41.         return min(arr, mid + 1, high);
  42.     }
  43. }

advertisement
Enter number of elements in array
10
Enter 10 elements of rotated sorted array
59 78 83 99 24 29 35 49 53 56
Minimum element = 24
 
 
Enter number of elements in array
10
Enter 10 elements of rotated sorted array
14 23 34 56 61 67 75 81 90 99
Minimum element = 14
 
 
Enter number of elements in array
10
Enter 10 elements of rotated sorted array
2 3 4 5 6 7 8 9 10 1
Minimum element = 1

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter