Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find smallest number in Sorted Rotatable Array

Tags:

algorithm

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.

like image 781
Lolly Avatar asked Dec 16 '11 10:12

Lolly


People also ask

How do you find the minimum element in an array using binary search?

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.


2 Answers

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 that
arr[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]
like image 70
codaddict Avatar answered Oct 05 '22 23:10

codaddict


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;
    }

}
like image 29
amit veerani Avatar answered Oct 05 '22 23:10

amit veerani