Find the Point of Rotation in Sorted Array

Problem Statement

You are given a sorted array. However, there is a problem. Someone just rotated the sorted array by K spaces and we do not know the value of K.

Write a program to find the value of K by which the array is rotated. As the array has millions of numbers, it would be good to have a solution which takes minimal time.

Approach to Find the Point of Rotation

Brute Force

Let us try out my favorite approach, the Brute Force Method. It is quite simple, below are the steps:

  • Start traversing the array from the beginning
  • There will be a index in the array where the value stored at the index will be smaller than the value at the previous index.
  • Return the index.

Ah! that was really simple.

Source Code:

Analysis:

As we traverse the whole array, the time taken is linear to the input size i.e. O(N). It requires constant space to maintain loop counters etc.

Efficient Solution

The above solution is great, however, the problem says efficient solution, and here is one. Remember our best friend, Binary Search?

If we notice, there is just one index in the complete array, where the numbers start decreasing.

  • Each number in the left of this point is greater than the last element in the array.
  • Each element in the right of this point is smaller than the last element in the array.
  • Lets find a middle index M in the range [L .. R] and probe it in comparison to the last element of the array
  • If the element is smaller than the last,
    • the point of rotation definitely lies in the left of the middle element
    • Hence, redefine the range for probing [L .. M – 1]
  • Else
    • The point of rotation certainly lies in the right of the middle element
    • Hence, redefine the range for probing [M+1, L]
  • Re-calculate the M and repeat the probing.
  • Terminate the loop when start is not less than or equal to end

And as I mentioned in the Binary Search post, there are numerous other ways how a Binary Search can be used and this is one of them. Notice that there was no input element to search but the point of rotation was to be searched.

Source Code:

Analysis:

As the code is a vanilla Binary Search, it has logarithmic running time O(logN). The space requirements remain same as constant O(1)

Conclusion

We learnt that Binary Search can be used not just for finding a given element but for other problems as well. A tip would be to revise and understand the implications of Binary Search. It can be used in numerous algorithms and the code is notoriously hard to write.