### Minimum Point in a Rotated Sorted Array

**Source:**Asked for a data scientist position at a technology startup in financial services sector in London

**Problem:**

What is the optimal algorithm to find the minimum element given a rotated sorted array of integers?

A rotated sorted array of integers is the output array of a rotation operation performed on a sorted array.

Eg: 3 5 6 1 2

Update (24 June 2014):

**Solution:**

Posted by Gaurav Bijay Kumar (CSE IITB 2006, Goldman Sachs Quant, Morgan Stanley Quant, Chicago Booth MBA, Credit Suisse IB, Goldman Sachs Strat), Sandeep, Khalil Sawant, Himanshu, ciddhi and gaurushh.

O(lg n)

ReplyDeleteFindMin( A )

If (n==1)

return A(0);

else

{

L = A[ 0 ... n/2-1 ];

R = A[ n/2 ... n-1 ];

if( L(0) <= L(n/2-1) and R(n/2) >= R(n-1) )

return FindMin( R );

else

return FindMin( L );

}

Yo. Awesome. Thanks

DeleteIt will not work for duplicate entries.

DeleteExample

11101111111

Its not working for

Delete5,6,7,8,9,10,1,2,3

If the array is sorted in increasing order then the minimum element is always the element next to the maximum (unless rotation is from starting element in which case max is last and min is first). Upon any other single rotation, the array is divided to two continuous and non decreasing parts such that all elements of the second part (i.e. with indices greater than first) are less than first lets call them A and B respectively. Now implement a traversal like binary search wherein we try to find the min element. Its the first element in B. At any position i, if F(i)>F(0) then its in A else in B. Using this idea, we discard portions of the array. We also check if F(i)>F(i-1). Once this is violated, we stop. The complexity is, as can be trivially seen, logarithmic in number of elements.

ReplyDeleteThanks

DeleteIf the array was sorted

ReplyDeletearr[start] <= arr[middle] <= arr[end]

Since the array is rotated, once of the above two conditions is violated

For the half that the condition is violated, repeat the iteration on that half of array

Recurse

Thanks

DeleteThis can be done in O(log(n)) using a binary search for the first element x that's smaller than it's previous element

ReplyDeleteYour solution needs to be elaborated. Thanks

Deletetake --> low -- mid -- high

ReplyDeleteif a[low]> a[mid] then

high=mid and find new mid

if a[low] < a[mid]

log = mid and find new mid

this is the basic algo, some special cases need to be added.

Thanks

Deleteint minPoint(int a[],int n)

ReplyDelete{

int mid=n/2;

if(n==1)

return 0;

if(a[mid-1]>a[mid])

return mid;

if(a[mid]>a[mid+1])

return mid+1;

if(a[0]a[n-1])

return mid+minPoint(a+mid+1,n-mid-1);

else

return minPoint(a,mid);

}

Other than a few mistakes in the code, in principal the solution looks correct. Thanks

DeleteIt can be done using binary search algorithm in O(logn).

ReplyDeleteSplit at mid point and check the first and last element of both the partitions. We go further in the one which has A[first element]>A[last element] (The order is opposite as should be as per the sorting).

Lets say if it is in increasing order, then the algo is:

DeleteYou compare a[n/2-1] and a[0]. If a[n/2-1] is bigger, then you compare a[0] with middle element of the partial array (a[n/2-1] to a[end]), else

you compare with the middle element of the partial array (a[0] to a[n/2-1]).

You continue like this until you have left with no space to move right or left. You will ultimately fall on the smallest.

In case of decreasing order, just switch the direction of movement.

Although this needs additional information of increasing or decreasing to make movements.

Thanks ciddhi and gaurushh.

Delete