CODEWITHSUNDEEP
algorithmbinary-search
TheOne
TheOne

Reputation: 11161

How to determine at which index has a sorted array been rotated around?

Given an array, such as [7,8,9,0,1,2,3,4,5,6], is it possible to determine the index around which a rotation has occurred faster than O(n)?

With O(n), simply iterate through all the elements and mark the first decreasing element as the index.

A possibly better solution would be to iterate from both ends towards the middle, but this still has a worst case of O(n).

Upvotes: 2

Views: 4265

Answers (6)

Shoaib Shaikh
Shoaib Shaikh

Reputation: 4585

Using a recursive method:

static void Main(string[] args) { var arr = new int[]{7,8,9,0,1,2,3,4,5,6}; Console.WriteLine(FindRotation(arr)); }

    private static int FindRotation(int[] arr)
    {
        var mid = arr.Length / 2;
        return CheckRotation(arr, 0, mid, arr.Length-1);
    }

    private static int CheckRotation(int[] arr, int start, int mid, int end)
    {
        var returnVal = 0;
        if (start < end && end - start > 1)
        {
            if (arr[start] > arr[mid])
            {
                returnVal = CheckRotation(arr, start, start + ((mid - start) / 2), mid);
            }
            else if (arr[end] < arr[mid])
            {
                returnVal = CheckRotation(arr, mid, mid + ((end - mid) / 2), end);
            }
        }
        else
        {
            returnVal = end;
        }

        return returnVal;
    }

Upvotes: 0

selftaught91
selftaught91

Reputation: 7471

Precondition

  • Array is sorted in ascending order
  • Array is left rotated

Approach

  • First we need to find the index at which smallest element is there.
  • The number of times array has been rotated will be equal to the difference of length of array and the index at which the smallest element is there.

so the task is to find the index of the smallest element. we can find the index of lowest element in two ways

Method 1 -

  • Just traverse the array and when the current element is smaller than the next element then the current index is the index of smallest element. In worst case this will take O(n)

Method 2

  • Find the middle element using (lowIndex+highIndex)/2
  • and then we need to find that in which side of the middle element we can find the smallest element because it can be found either left or right of the middle elment
  • we compare the first element to the middle element and if first element is greater than the middle element then it means smallest element lies in the left side of middle element and
  • if the first element is smaller than the middle element then lowest element can be found in the right side of the middle element

so this can be applied like a binary search and in O(log(n)) we cab find the index of smallest element

Upvotes: 0

siddharth
siddharth

Reputation: 21

For an array of N size if the array has been rotated minimum 1 time and less than N times, i think it will work fine:

int low=0, high = n-1;
int mid = (low +high)/2;
while( mid != low && mid != high)
 {
  if(a[low] < a[mid])
  low = mid;
  else
  high = mid;
  mid = (low + high)/2;
 }
return high;

Upvotes: 2

Dennis Meng
Dennis Meng

Reputation: 5187

(EDIT: The below assumes that elements are distinct. If they aren't distinct, I don't think there's anything better than just scanning the array.)

You can binary search it. I won't post any code, but here's the general idea: (I'll assume that a >= b for the rest of this. If a < b, then we know it's still in its sorted order)

Take the first element, call it a, the last element b, and the middle element, calling it c.

If a < c, then you know that the pivot is between c and b, and you can recurse (with c and b as your new ends). If a > c, then you know that the pivot is somewhere between the two, and recurse in that half (with a and c as ends) instead.

ADDENDUM: To extend to cases with repeats, if we have a = c > b then we recurse with c and b as our ends, while if a = c = b, we scan from a to c to see if there is some element d such that it differs. If it doesn't exist, then all of the numbers between a and c are equal, and thus we recurse with c and b as our ends. If it does, there are two scenarios:

a > d < b: Here, d is then the smallest element since we scanned from the left, and we're done.
a < d > b: Here, we know the answer is somewhere between d and b, and so we recurse with those as our ends.

In the best case scenario, we never have to use the equality case, giving us O(log n). Worst case, those scans encompass almost all of the array, giving us O(n).

Upvotes: 3

unkulunkulu
unkulunkulu

Reputation: 11922

One observation is that the shift is equal to the index of the minimal element. So all you have to do is to use the binary search to find the minimal element. The only catch is that if the array has the equal elements, the task gets a bit tricky: you cannot achieve a better big O efficiency than O(N) time because you can have in input like [0, 0, 0, 0, ..., 100, 0, 0, 0, ..., 0] where you cannot find the only non-zero element quicker than linearly of course. But still the following algorithm achieves O(Mins + Log(N)) where Mins is the number of minimal elements iff the array[0] is one of the minima (otherwise Mins = 0 giving no penalty).

l = 0;
r = len(array) - 1;
while( l < r && array[l] == array[r] ) {
    l = l + 1;
}

while( l < r ) {
    m = (l + r) / 2;
    if( array[m] > array[r] ) {
        l = m + 1;
    } else {
        r = m;
    }
}

// Here l is the answer: shifting the array l elements left will make it sorted

This works in O(log N) for unique-element arrays and O(N) for non-unique element ones (but still faster than a naive solution for majority of inputs).

Upvotes: 0

bmm6o
bmm6o

Reputation: 6515

You can use a binary search. If you pick 1 as the central value, you know the break is in the first half because 7 > 1 < 6.

Upvotes: 1

Related Questions