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.

 (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.
 */
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];
    }
}