MinSortedRotatedArray.java

package binary_search;

/**
 * Created by gouthamvidyapradhan on 10/04/2017. Suppose an array sorted in ascending order is
 * rotated at some pivot unknown to you beforehand.
 *
 * <p>(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 *
 * <p>Find the minimum element.
 *
 * <p>You may assume no duplicate exists in the array.
 */
public class MinSortedRotatedArray {
  /**
   * Main method
   *
   * @param args
   * @throws Exception
   */
  public static void main(String[] args) throws Exception {
    int[] A = {5, 1, 2, 3, 4};
    System.out.println(new MinSortedRotatedArray().findMin(A));
  }

  public int findMin(int[] nums) {
    if (nums.length == 0) return 0;
    else if (nums.length == 1) return nums[0];
    int low = 0, high = nums.length - 1;
    while (low < high) {
      int mid = (low + high) / 2;
      if (mid > 0 && nums[mid] < nums[mid - 1]) return nums[mid];
      if (nums[low] > nums[mid]) high = mid - 1;
      else if (nums[high] < nums[mid]) low = mid + 1;
      else high = mid - 1;
    }
    return nums[low];
  }
}