Problem : We have to find an element which is having lowest value in the given array which is sorted and rotated. FYI: This question was asked me in oracle interview.(All elements of the array are unique)
what is sorted and rotated array ?
Sorted array (ONLY) :
By brute force approach we can find that element in O(n) , off course this is not expected answer
any interviewer would like to hear at least not in F2F interview :P
So what next ? Since we have a sorted array and we have to find a solution better than O(n) so Binary search may be handy to solve this problem. If we see diagram closely we can find that main rationale behind this problem is :
If (array is rotated )
lowest element is that element whose previous element is always higher
else
first element is lowest element.
Algorithm : Do simple binary search
find middleIndex from startIndex and endIndex of array
if (element@middleIndex > element@(middleIndex+1))
lowest element is element@(middle+1)
return "we are done!!"
else if (element@middleIndex < element@(middleIndex-1))
lowest element is element@(middle)
return "we are done!!"
else
if(element@middleIndex < element@endIndex)
Do not move in right direction , since elements are in increasing order.
go to left direction and repeat binary search methd
else
Do not move in left direction , since elements are in increasing order.
go to right direction and repeat binary search methd
Now we will write the sample java code for this . public class FindMinimumInRotatedArray {
public FindMinimumInRotatedArray() {
super();
}
private int findMinInSortedAndRotated(int arr[], int low, int high)
{
// Added to handle the case when array is not
// rotated at all
if (high < low) return arr[0];
// If there is only one element left
if (high == low) return arr[low];
// Find mid
int mid = low + (high - low)/2; /*To avoid overflow do not use (low + high)/2;*/
if (mid < high && arr[mid+1] < arr[mid])
return arr[mid+1];
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return arr[mid];
// Decide whether we need to go to left half or right half
if (arr[high] > arr[mid])
return findMin(arr, low, mid-1);
return findMin(arr, mid+1, high);
}
public static void main(String[] args) {
FindMinimumInRotatedArray findMinimumInRotatedArray = new FindMinimumInRotatedArray();
int[] arr = { 6, 7, 8, 9, 1, 2, 3, 4, 5 };
System.out.println(findMinimumInRotatedArray.findMinInSortedAndRotated(arr, 0, 9));
}
}
Sample output : 1when we execute program we will get 1 output , since it is minimum element.
Now if we twist the question little bit what will happen if all elements of the array are not unique.
-------------------------------------------------------------------------------------------------------
Happy learning!!
Nikhil