I came across this question in one Interview. Please help me in getting the solution.
Question is:
You have sorted rotatable array, i. e. the array contains elements which are sorted and it can be rotated circularly, like if the elements in array are [5,6,10,19,20,29] then rotating first time array becomes [29,5,6,10,19,20] and on second time it becomes [20,29,5,6,10,19] and so on.
So you need to find the smallest element in the array at any point. You won’t be provided with number times array is rotated. Just given the rotated array elements and find out the smallest among them. In this case output should be 5.
In Binary Search, we first calculate the mid. To find the minimum element we can compare mid with mid-1 and mid+1 element. If it is not found at mid then the minimum element lies either in left or right half. i) If the middle element is smaller than the last element, then the minimum element lies in the left half.
Method 1:
You can do this in O(logN)
time.
Use a modified binary search to find the point of rotation which is an index i
such thatarr[i] > arr[i+1]
.
Example:
[6,7,8,9,1,2,3,4,5]
^
i
The two sub-arrays (arr[1], arr[2], .., arr[i])
and(arr[i+1], arr[i+2], ..., arr[n])
are sorted.
The answer is min(arr[1], arr[i+1])
Method 2:
When you split the sorted, rotated array into two halves (arr[1],..,arr[mid])
and (arr[mid+1],..,arr[n])
, one of them is always sorted and the other always has the min. We can directly use a modified binary search to keep searching in the unsorted half
// index of first element
l = 0
// index of last element.
h = arr.length - 1
// always restrict the search to the unsorted
// sub-array. The min is always there.
while (arr[l] > arr[h]) {
// find mid.
mid = (l + h)/2
// decide which sub-array to continue with.
if (arr[mid] > arr[h]) {
l = mid + 1
} else {
h = mid
}
}
// answer
return arr[l]
The above algorihtm fails if data element is repeated like {8,8,8,8,8} or {1,8,8,8,8} or {8,1,8,8,8} or {8,8,1,8,8} or {8,8,8,8,1}
// solution pasted below will work all test cases :)
//break the array in two subarray and search for pattern like a[mid]>a[mid+1]
// and return the min position
public static int smallestSearch(int[] array,int start,int end)
{
if(start==end)
return array.length;
int mid=(start+end)/2;
if(array[mid]>array[mid+1])
return min(mid+1,smallestSearch(array,start,mid),smallestSearch(array,mid+1,end));
else
return min(smallestSearch(array,start,mid),smallestSearch(array,mid+1,end));
}
public static int min(int a,int b)
{
if(a==b)
return a;
else if(a<b)
return a;
else
return b;
}
public static int min(int a,int b,int c)
{
if(a<c)
{
if(a<b)
{
return a;
}
else
{
return b;
}
}
else
{
if(b<c)
return b;
else
return c;
}
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With