Array Find Minimum In Rotated Sorted Array LeetCode

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

NOTE:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

This is a classical interview question and is very popular in LeetCode and GeeksForGeeks A collection of hundreds of interview questions and solutions are available in our blog at Interview Question Solutions

Solution:

	/**
	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.
	Example 1:
	Input: [3,4,5,1,2]
	Output: 1
	Example 2:
	Input: [4,5,6,7,0,1,2]
	Output: 0
	*/
	public class ArrayFindMinimumInRotated{
	/**
	-use binary search
	-find the peak from where the sorted order is violated, this gives the two halves of the array
	-if the peak is in the middle, then the smallest element will be just after the peak
	-if the peak is at the end, then the smallest element is at 0 index
	-we assume there is no duplicate
	*/
	public static int findMin(int[] nums) {
	//base cases
	if(nums==null || nums.length<1){
	return -1;
	}
	int index = 0;
	int start = 0, end = nums.length;
	while((index+1)<end && nums[index]<nums[index+1]){
	index++;
	}
	//now if the index is at the middle, then the smallest will be just after the index
	if(index<end-1){
	return nums[index+1];
	}else{
	return nums[0];
	}
	}
	public static void main(String[] args){
	int[] nums = {4,5,6,7,0,1,2};
	System.out.println("min is found as:"+findMin(nums));
	nums = new int[]{3,4,5,1,2};
	System.out.println("min is found as:"+findMin(nums));
	nums = new int[]{1, 3};
	System.out.println("min is found as:"+findMin(nums));
	}
	}

view raw ArrayFindMiniumumInRotatedSortedArray.java hosted with ❤ by GitHub