Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

  1. public class Solution {
  2.   public int findMin(int[] a) {
  3.     return search(a, 0, a.length - 1);
  4.   }
  6.   int search(int[] a, int lo, int hi) {
  7.     // a[] is sorted
  8.     if (lo > hi) {
  9.       return a[0];
  10.     }
  12.     int mid = lo + (hi - lo) / 2;
  14.     if (mid > 0 && a[mid - 1] > a[mid]) {
  15.       return a[mid];
  16.     }
  18.     if (mid < a.length - 1 && a[mid] > a[mid + 1]) {
  19.       return a[mid + 1];
  20.     }
  22.     if (a[mid] < a[hi]) {
  23.       return search(a, lo, mid - 1);
  24.     } else {
  25.       return search(a, mid + 1, hi);
  26.     }
  27.   }
  28. }